Quy tắc in văn bản trong máy vi tính là không được có chữ nào hiển thị trên 2 dòng(1 chữ sẽ được hiển thị trọn vẹn trên 1 dòng). Hãy tính xem với đầu vào là một chuỗi máy tính cần bao nhiêu dòng để có thể hiển thị đủ văn bản đó

Chi tiết như sau:

• Mỗi chữ cái sẽ được quy định chiều rộng bằng một số cố định trong khoảng [1,9] (tính theo đơn vị pixel)
• Quy ước với dấu cách (khoảng trắng) có chiều rộng = 2pixel.
• Độ rộng màn hình mặc định là 100pixel
• Các chữ cái liền nhau sẽ không mất thêm khoảng cách giữa chúng.
  • (Ví dụ: \(a = 2 pixel, b = 3 pixel \implies 'a b' = 7 pixel = 2 + 2 + 3)\)
• Nếu tới cuối trang giấy mà từ đang hiển thị vừa đủ hết chiều rộng màn hình thì ở dòng tiếp theo sẽ hiển thị luôn tới từ kế tiếp mà không cần phải hiển thị khoảng trắng. ### Ví dụ:
• 'một hai ba' nếu như dòng đầu tiên chỉ chứa vừa đủ 'một hai' thì dòng tiếp theo chỉ cần viết 'ba' là được mà không cần phải có dấu cách ở trước từ 'ba'. Trong trường hợp đang hiển thị dở 1 từ thì hết dòng, cần phải chuyển từ đó xuống dòng dưới.
• 'mười hai ba bốn' đang tới 'mười hai b' thì hết dòng, thì chỉ được hiển thị 'mười hai ' và dòng tiếp theo sẽ là 'ba bốn'. Quy tắc này sẽ đảm bảo 1 từ luôn được trọn vẹn trên một dòng(chánh trường hợp có 1 phần ở dòng trên và 1 phần ở dòng dưới)

Đầu vào:

• Một số nguyên T \((1 \leq T \leq 100)\) là số đoạn văn cần hiển thị.
• 26 dòng tiếp theo mỗi dòng có định dạng X Y. X là chữ cái từ \(a - z\) viết thường, Y là số nguyên (\(1 \leq Y \leq 9\)).
  • Giải thích: với chữ cái \(X\) sẽ quy ước có độ rộng \(= Y\), thứ tự của 26 dòng này không nhất thiết phải theo bảng chữ cái.
• T dòng tiếp theo, dòng thứ \(i\) chứa 1 chuỗi ghi nội dung của đoạn văn thứ \(i\), mỗi đoạn văn đảm bảm chỉ có các kí tự thường \(a - z\) và khoảng trắng, mỗi từ có khoảng (2, 5) ký tự, mỗi đoạn văn có khoảng 5 tới 500 từ và đảm bảo cuối đoạn không có khoảng trắng.

Đầu ra:

• \(T\) dòng, dòng thứ i ghi 1 số nguyên là số dòng cần có để hiển thị đoạn văn thứ \(i\).

Ví dụ:

Input

2
p 1
n 2
c 3
k 1
r 2
u 3
z 1
h 2
j 3
i 1
w 2
g 3
d 1
o 2
f 3
a 9
q 2
aaa aa a a aa a
aaa aa a a aa aa

Output

1
2

Giải thích:

• Với dòng đầu tiên : 'aaa aa a a aa a' có 10 chữ a và 5 khoảng trắng nên có độ rộng vừa = 100 nên chỉ mất 1 dòng.
• Với dòng thứ hai: 'aaa aa a a aa aa' khi viết được 15 kí tự đầu tiên thì đã hết dòng, tuy nhiên đang viết dở chữ cuối cùng, vậy cần mang chữ cuối cùng đó viết sang dòng mới. ta được kết quả 2 dòng như sau
  • Dòng 1: 'aaa aa a a aa '
  • Dòng 2: 'aa'