To read the problem statement in English, choose the language using the flag on the navigation bar.

Sau khi dịch COVID-19 được đẩy lùi trên hành tinh mèo, chính phủ vừa gỡ bỏ quy định giãn cách xã hội. Neko, sau hơn một năm phải ở nhà vì dịch, đã quyết định đi du lịch tại thành phố Uwutopia, một thành phố du lịch nổi tiếng với cảnh quan tuyệt đẹp (và các công trình kiến trúc lấy cảm hứng từ mèo - loài vật thống trị trên hành tinh này).

Có ~m~ địa điểm tại thành phố, được đánh số từ ~1~ đến ~m~. Neko đã liên hệ với một công ty du lịch gần nhà và biết được công ty hiện đang tổ chức ~n~ tour du lịch, tour thứ ~i~ sẽ tham quan các địa điểm được đánh số từ ~l_i~ đến ~r_i~. Vì đã lâu rồi không được đi du lịch, cậu quyết định sẽ đăng kí đi một lúc hai tour du lịch cho thỏa thích. Tuy nhiên, cậu cảm thấy việc tham quan một nơi đến hai lần sẽ rất nhàm chán, nên cậu muốn rằng hai tour du lịch không có địa điểm nào chung.

Hãy giúp Neko tìm ra cặp tour du lịch bất kì thỏa yêu cầu của cậu, hoặc thông báo với cậu trong trường không tồn tại cặp tour du lịch nào như vậy. Nếu có nhiều cặp tour du lịch thỏa mãn yêu cầu, hãy chỉ ra một cặp tour bất kì.

Input

Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ (~2 \le n \le 10^5~, ~1 \le m \le 10^9~), lần lượt là số tour du lịch và số địa điểm du lịch.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa hai số nguyên ~l_i~ và ~r_i~ (~1 \le l_i \le r_i \le m~), là mô tả của tour thứ ~i~.

Output

Nếu tồn tại hai tour du lịch thỏa mãn yêu cầu đề bài, dòng đầu tiên in ra YES, dòng thứ hai in ra hai số nguyên ~i~ và ~j~ (~1 \le i, j \le n~, ~i \neq j~) là chỉ số của hai tour du lịch cần tìm. Nếu có nhiều cặp tour du lịch thỏa mãn yêu cầu, hãy chỉ ra một cặp tour bất kì.

Ngược lại, in ra NO trên một dòng duy nhất.

Scoring

• Subtask 1, tương ứng với ~15~ điểm, có ~n = 2~, ~m \le 100~.

• Subtask 2, tương ứng với ~15~ điểm, ~n \le 1000~.

• Subtask 3, tương ứng với ~20~ điểm, không có giới hạn gì thêm.

Tổng cộng bài toán này có ~50~ điểm.

Sample Input 1

4 5
1 3
1 2
3 5
4 4

Sample Output 1

YES
4 2

Sample Input 2

4 10
1 4
2 5
3 6
4 7

Sample Output 2

NO

Sample Input 3

2 10
1 4
6 10

Sample Output 3

YES
1 2

Sampe Input 4

2 10
1 5
5 10

Sample Output 4

NO

Notes

Ở ví dụ đầu tiên, cặp tour du lịch ~(1, 4)~, ~(2, 3)~ hoặc ~(2, 4)~ cũng là những đáp án hợp lệ.

To read the problem statement in English, choose the language using the flag on the navigation bar.

Center Supermeowket là hệ thống siêu thị lớn nhất trên hành tinh mèo. Hiện tại, siêu thị đang tiến hành chương trình khuyến mãi đặc biệt với thể lệ như sau:

Có ~n~ gói khuyến mãi, mỗi gói khuyến mãi gồm ~m~ phần quà. Phần quà thứ ~j~ của gói khuyến mãi thứ ~i~ có giá trị là ~A_{i, j}~. Các phần quà trong cùng một gói khuyến mãi sẽ có giá trị không giảm (phần quà sau sẽ có giá trị lớn hơn hoặc bằng phần quà trước).

Khách hàng có thể đổi quà khuyến mãi bằng điểm khách hàng thân thiết (KHTT). Cụ thể, với mỗi gói khuyến mãi, khách hàng có thể đổi ~x~ điểm (với ~0 \le x \le m~) để nhận ~x~ món quà đầu tiên của gói. Lưu ý rằng, chỉ có thể đổi điểm tối đa một lần với mỗi gói. Và hiển nhiên, tổng số điểm dùng để đổi quà không thể lớn hơn số điểm KHTT hiện có.

Neko, một khách hàng lâu năm của Center Supermeowket, hiện tại đang có ~k~ điểm KHTT. Cậu muốn biết rằng, với cách đổi quà tối ưu thì tổng giá trị tối đa của các phần quà mà cậu nhận được là bao nhiêu.

Input

Dòng đầu tiên gồm ba số nguyên ~n~, ~m~, ~k~ (~1 \le n \le 10^5~, ~1 \le m \le 10~, ~1 \le k \le n \cdot m~), lần lượt là số gói khuyến mãi, số phần quà trong mỗi gói và số điểm KHTT hiện có.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa ~m~ số nguyên dương ~A_{i,1}, A_{i,2}, \ldots, A_{i,m}~ (~1 \le A_{i,1} \le A_{i,2} \le \ldots \le A_{i,m} \le 10^9~), lần lượt là giá trị của các phần quà trong gói khuyến mãi thứ ~i~.

Output

In ra một số nguyên duy nhất là tổng giá trị các phần quà tối đa có thể đổi được.

Scoring

• Subtask 1, tương ứng với ~30~ điểm, có ~n \le 15~ và ~m = 2~

• Subtask 2, tương ứng với ~45~ điểm, có ~n \le 300~

• Subtask 3, tương ứng với ~75~ điểm, không có giới hạn gì thêm

Tổng cộng bài toán này có ~150~ điểm.

Sample Input 1

3 2 3
1 3
2 9
7 8

Sample Output 1

18

Notes

Neko sẽ đổi 2 phần quà ở gói thứ hai, và 1 phần quà ở gói thứ ba. Tổng giá trị quà nhận được là ~2 + 9 + 7 = 18~.

To read the problem statement in English, choose the language using the flag on the navigation bar.

Phát có em gái rất siêng năng học hỏi. Tuy nhiên môn lịch sử lúc nào cũng là trở ngại đối với em gái của Phát, do đó Phát sẽ kèm em gái của mình học môn lịch sử. Hôm nay hai bạn sẽ ôn lại về tầm ảnh hưởng của phát triển công nghệ ảnh hưởng thế nào đến các quốc gia trên thế giới.

Như chúng ta đã biết, trên thế giới có ~n~ quốc gia tồn tại và phát triển đọc lập với nhau. Phát sẽ giúp em gái ôn lại một số sự kiện nổi bật sau:

• Đầu tiên là sự ra đời và phát triển của máy bay và đường hàng không. Cho đến nay, máy bay vẫn là phương tiện nhanh chóng và an toàn nhất. Xây dựng sân bay và sử dụng đường hàng không là một bước không thể thiếu đối với một quốc gia có nền công nghệ phát triển. Tại một thời điểm nào đó, sẽ có hai quốc gia ~u~ và ~v~ mở tuyến đường hàng không qua lại với nhau. Sau sự kiện này, mọi người có thể bay từ quốc gia ~u~ sang quốc gia ~v~, và ngược lại.

• Hợp tác quốc tế trong lĩnh vực công nghệ cũng là một hướng phát triển trong lĩnh vực này. Tại một thời điểm nào đó, sẽ có hai quốc gia ~x~ và ~y~ kí hiệp ước hợp tác với nhau trong lĩnh vực công nghệ.

• Sự kiện đáng chú ý nhất trong lịch sử có lẽ là một phát kiến công nghệ. Khi một quốc gia ~k~ có một phát kiến công nghệ, quốc gia này sẽ gửi thư mời các đại sứ, cũng như các kĩ sư của các nước mà quốc gia này đã có hiệp ước trước đó đến quốc gia ~k~ để tham gia hội thảo về công nghệ mới nhất này. Tuy nhiên, hội thảo chỉ diễn ra trong thời gian ngắn, nên các khác mời được mời đến phải sử dụng đường hàng không để đến kịp hội thảo. Máy bay di chuyển rất nhanh, nên các khách mời có thể bay qua một số quốc gia trung gian. Tuy nhiên, nếu quốc gia ~h~ nhận được thư mời từ quốc gia ~k~, nhưng từ quốc gia ~h~ không có tuyến bay nào đến quốc gia ~k~, vậy quốc gia ~h~ sẽ không cử đại diện đến tham dự hội thảo.

Phát đã giảng lại cho em của mình ~q~ sự kiện trên theo trình tự thời gian, nhưng em gái vẫn khó thể nào mà nhớ được các sự kiện này. Để giúp em gái của mình có có ấn tượng tốt hơn về các sự kiện, Phát đố: với mỗi mội thảo, hãy tính xem có bao nhiêu quốc gia có thể cử đại diện đến tham gia được hội thảo này.

Cho biết có ~n~ quốc gia độc lập, ban đầu chưa thiết lập đường bay đến nhau, cũng như chưa hiệp ước nào được kí, và cho biết danh sách ~q~ sự kiện được diễn ra theo trình tự thời gian. Hãy giúp em gái của Phát trả lời câu đố của phát cho từng sự kiện hội thảo.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~1 \le n \le 2 \cdot 10^5~, ~1 \le q \le 6 \cdot 10^5~), lần lượt là số lượng quốc gia và số sự kiện mà Phát đã giảng cho em gái.

Mỗi dòng trong ~q~ dòng tiếp theo mô tả các sự kiện theo mô tả sau:

• 1 u v  – mô tả sự kiện quốc gia ~u~ và ~v~ (~1 \le u, v \le n~, ~u \ne v~) mở tuyến đường hàng không qua lại với nhau. Dữ liệu đảm bảo trước đó quốc gia ~u~ và ~v~ chưa thiết lập đường hàng không với nhau.

• 2 x y  – mô tả sự kiện quốc gia ~x~ và ~y~ (~1 \le x, y \le n~, ~x \ne y~) kí hiệp ước hợp tác với nhau trong lĩnh vực công nghệ. Dữ liệu đảm bảo trước đó quốc gia ~x~ và ~y~ chưa kí hiệp ước hợp tác với nhau.

• 3 k  – mô tả sự kiện quốc gia ~k~ (~1 \le k \le n~) có phát kiến công nghệ mới và gửi thư mời các quốc gia đã có hiệp ước với quốc gia ~k~ trước đó đến quốc gia ~k~ để tham gia hội thảo về công nghệ. Dữ liệu đảm bảo có ít nhât một sự kiện loại này.

Output

Với mỗi sự kiện hội thảo (tức sự kiện loại 3), hãy in ra số lượng các quốc gia có thể cử đại diện tham gia hội thảo công nghệ.

Scoring

• Subtask 1, tương ứng với ~80~ điểm, có ~n \leq 10^3~ và ~q \leq 3 \cdot 10^3~.

• Subtask 2, tương ứng với ~125~ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán này có ~205~ điểm.

Sample Input 1

4 8
1 1 3
2 1 4
3 1
1 4 1
2 1 2
3 4
1 2 4
3 1

Sample Output 1

0
1
2

Notes

Sự kiện hội thảo đầu tiên do quốc gia ~1~ tổ chức. Trước đó quốc gia ~1~ và ~4~ đã kí hiệp ước với nhau, nhưng quốc gia ~1~ mới chỉ có đường bay đến quốc gia ~3~, nên lúc đó quốc gia ~4~ không thể cử đại diện đến tham gia hội thảo được.

Sự kiện hội thảo tiếp theo do quốc gia ~4~ tổ chức. Lúc này từ quốc gia ~1~ đã có thể bay trực tiếp đến quốc gia ~4~. Lưu ý, quốc gia ~2~ không có hiệp ước với quốc gia ~4~, mà chỉ có hiệp ước với quốc gia ~1~.

Ở sự kiện hội thảo cuối cùng, quốc gia ~1~ lại tổ chức. Lúc này cả hai quốc gia ~2~ và ~4~ đều có thể cử đại diện đến hội thảo. Từ quốc gia ~4~ có thể bay trực tiếp đến quốc gia ~1~, còn từ quốc gia ~2~ đến cần bay đến quốc gia ~4~, rồi từ quốc gia ~4~ bay đến quốc gia ~1~ để tham gia hội thảo.

To read the problem statement in English, choose the language using the flag on the navigation bar.

Nhân ngày sinh nhật em gái của mình, Phát đã đặt mua một chiếc bánh lớn được trang trí bởi một dãy nến với đủ loại màu sắc. Trên bánh có ~n~ cây nến có màu sắc lần lượt là ~c_1, c_2, \ldots, c_n~ từ trái qua phải.

Em gái của Phát thích lắm! Sau khi thổi nến xong, em gái ngoan muốn cắt miếng bánh đầu tiên mời anh trai của mình. Để cắt một miếng bánh, em gái cần chọn hai chỉ số ~l~ và ~r~ (~1 \le l \le r \le n~), và miếng bánh được cắt ra sẽ bao gồm các cây nến với màu sắc ~c_l, c_{l + 1}, \ldots, c_r~.

Rất quý mến anh trai Phát, em gái muốn miếng bánh được cắt ra phải là miếng bánh rực rỡ. Miếng bánh được gọi là rực rỡ nếu như với mỗi màu sắc của từng cây nến trên miếng bánh, tồn tại đúng ~k~ cây nến với màu sắc đó trên miếng bánh, với ~k~ là số lớn nhất mà em gái đã đếm được trên đầu ngón tay.

Ví dụ, với ~k = 2~, miếng bánh từ dãy nến ~[1, 4, 1, 2, 2, 4]~ là một miếng bánh rực rỡ: trên miếng bánh này tồn tại hai cây nến có màu ~1~, hai cây nến có màu ~2~ và hai cây nến có màu ~4~. Ngược lại, chiếc bánh ~[1, 1, 2, 3]~ không rực rỡ, bởi vì nhưng chỉ có một cây nến có màu ~2~ và một cây nến có màu ~3~.

Hiện tại em gái đang có ~q~ cách cắt bánh. Với mỗi cách thứ ~i~, em gái muốn cắt bánh từ vị trí ~l_i~ đến ~r_i~. Hãy giúp em gái kiểm tra xem, với từng cách cắt, miếng bánh được cắt theo cách đó có rực rỡ không. Nếu như miếng bánh không rực rỡ, hãy giúp em gái chỉ ra một màu sắc với số lượng cây nến trên miếng bánh dương nhưng khác ~k~, để em gái có thể trang trí lại miếng bánh cho rực rỡ!. Nếu có nhiều màu như vậy, hãy in ra màu bất kì.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1 \le n \le 10^6~, ~1 \le k \le 5~), lần lượt là số lượng cây nến trên chiếc bánh và số lớn nhất hiện tại mà em gái của Phát đã đếm được.

Dòng tiếp theo chứa ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ (~1 \le c_i \le n~, với mọi ~1 \le i \le n~) là màu sắc của các cây nến trên chiếc bánh theo thứ tự từ trái qua phải.

Dòng tiếp theo chứa số nguyên ~q~ (~1 \le q \le 10^6~) là số lượng cách cắt bánh mà em gái có.

Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa hai số nguyên ~l_i~ và ~r_i~ (~1 \le l_i \le r_i \le n~) thể hiện một cách cắt bánh bao gồm các cây nến từ vị trí ~l_i~ đến ~r_i~ trên chiếc bánh.

Output

Hãy in ra ~q~ dòng. Trên dòng thứ ~i~ hãy in ra ~0~ nếu như miếng bánh với cách cắt thứ ~i~ là miếng bánh rực rỡ. Ngược lại, in ra chỉ số của màu với số lượng cây nến trên miếng bánh lớn hơn ~0~ nhưng khác ~k~. Nếu có nhiều màu thỏa mãn, hãy in ra màu bất kì.

Scoring

• Subtask 1, tương ứng với ~80~ điểm, có ~n \le 1000~ và ~q \le 1000~.

• Subtask 2, tương ứng với ~180~ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán này có ~260~ điểm.

Sample Input 1

9 2
1 3 1 3 2 2 1 1 2
9
1 6
2 7
5 8
6 9
7 8
1 4
3 6
4 8
2 8

Sample Output 1

0
0
0
0
0
0
1
3
1

Notes

Trong ví dụ, số lớn nhất mà em gái của Phát đã đếm được trên đầu ngón tay là ~k = 2~.

Với cách cắt đầu tiên, ~l = 1~, ~r = 6~. Các cây nến trên miếng bánh này có màu tạo thành dãy ~[1, 3, 1, 3, 2, 2]~. Đây là miếng bánh rực rỡ, vì trên miếng bánh có hai cây nến có màu ~1~, hai cây nến có màu ~2~ và hai cây nến có màu ~3~.

Với cách cắt thứ 6, ~l = 1~, ~r = 4~. Các cây nến trên miếng bánh này có dãy màu là ~[1, 3, 1, 3]~. Đây cũng là miếng bánh rực rỡ, vì trên miếng bánh có hai cây nến màu ~1~, hai cây nến màu ~3~, và không có cây nến màu khác.

Với cách cắt thứ 7, ~l = 3~, ~r = 6~. Các cây nến trên miếng bánh này có các màu lần lượt là ~[1, 3, 2, 2]~. Miếng bánh này không rực rỡ do chỉ có một cây nến màu ~1~ và một cây nến màu ~3~. Do đó ~1~ hoặc ~3~ là đáp án cho cách cắt này.

Với cách cắt cuối cùng, ~l = 2~, ~r = 8~. Các cây nến trên miếng bánh này có màu tạo biểu diễn bởi dãy ~[3, 1, 3, 2, 2, 1, 1]~. Miếng bánh này không rực rỡ, do số lượng cây nến với màu ~1~ là ba.

To read the problem statement in English, choose the language using the flag on the navigation bar.

Ngày xửa ngày xưa, ở một ngôi làng nọ, có một phú ông giàu có. Phú ông có một cô con gái hiền lành, nết na. Trong ngôi làng, cũng có tiều phu, rất cần cù chịu khó. Thấy anh tiều phu rất siêng năng, phú ông rất muốn thuê anh tiều phu. Phú ông hứa: "Con chịu khó làm lụng giúp ta, ba năm nữa ta sẽ gả con gái ta cho". Tin lời phú ông, anh tiều phu vất vả ngày đêm lên rừng kiếm thật nhiều củi. Sau ba năm, phú ông đã giàu lên một phần là nhờ công sức cực nhọc của anh tiều phu. Tuy vậy, phú ông lại trở mặt, không muốn gả con gái cho anh tiều phu. Để gây khó khăn cho anh tiều phu, phú ông thách thức anh tiều phu, cần phải lên rừng kiếm cây tre ngàn đốt về để xây nhà thì ông mới gả con gái cho. Thật thà tin lời phú ông, anh tiều phu nhanh chóng lên rừng tìm cây tre. Nhưng tìm mãi không thấy, nên anh tiều phu buồn tủi, ngồi vào bờ tre và khóc. Lúc đó ông Bụt hiện lên, hỏi han anh tiều phu. Sau khi nghe anh tiều phu giải thích, ông Bụt bảo anh tiều phu đốn tre sao cho tổng cộng đủ một ngàn dốt và đem về đây. Sau đó, ông Bụt dạy anh tiều phu câu thần chú "Khắc nhập, khắc nhập", và toàn bộ cây tre mà anh tiều phu đã đốn gộp lại thành một.

Sự việc diễn ra ở xứ sở VNOI, nên mỗi đốt của của cây tre đều có một kí tự tiếng Anh in thường, do đó mỗi một cây tre có thể được biểu diễn bởi một xâu kí tự, với kí tự đầu tiên là kí tự ở đốt gốc và kí tự cuối cùng là kí tự của đốt ngọn. Câu thần chú của "Khắc nhập, khắc nhập" cũng là câu thần chú đặc biệt: các cây tre sẽ được nối lại thành một cây tre có thứ tự từ điển nhỏ nhất!

Minh họa cho câu thần chú "Khắc nhập, khắc nhập" cho 4 cây tre biểu diễn bởi các xâu tre, is, a, long và tree. Câu thần chú nối các cây tre lại thành cây biểu diễn bởi xâu aislongtreetre và đây là cây có xâu biểu diễn có thứ tự từ điển nhỏ nhất.

Nhưng mang một cây tre một ngàn đốt từ rừng về làng quả là vất vả. Do đó ông Bụt dạy anh tiều phu thêm một câu thần chú nữa là "Khắc xuất, khắc xuất". Sau khi đọc câu thần chú này, cây tre một trăm đốt này sẽ bị cắt thành một vài cây tre nhỏ hơn. Như vậy anh tiều phu có thể mang các cây tre này về làng dễ hơn, rồi sử dụng câu thần chú "Khắc nhập, khắc nhập" để lại tạo ra cây tre ngàn đốt.

Minh họa cho câu thần chú "Khắc xuất, khắc xuất" cho cây tre biểu diễn bởi xâu aislongtreetre thành các cây tre biểu diễn bởi xâu aisl, ongtre và etre. Lưu ý đây không phải là cách duy nhât sử dụng câu thần chú này để chia cắt cây tre.

Để qua được con mắt tinh tường của phú ông, anh tiều phu cần đảm bảo rằng, nếu như gọi câu thần chú "Khắc xuất, khác xuất", sau đó lại gọi "Khắc nhập, khắc nhập", xâu kí tự của cây tre ngàn đốt mới không đổi so với cây tre ngàn đốt cũ. Nếu hai cây tre khác nhau, phú ông có thể dễ dàng phát hiện đây là những cây tre đã bị cắt và nối lại. May mắn thay, với câu thần chú "Khắc xuất, khắc xuất", anh tiều phu có thể chọn vị trí cắt các cây tre.

Cho xâu kí tự ~S~ là xâu kí tự biểu diễn cây tre ngàn đốt (độ dài của ~S~ không nhất thiết phải là ~1000~, vì ngàn là tên gọi). Hãy đếm số cách sử dụng câu thần chú "Khắc xuất, khắc xuất" để cắt cây tre này, sau đó lại gọi câu thần chú "Khắc nhập, khắc nhập", thu được cây tre vẫn mà có thể biểu diễn bởi xâu kí tự ~S~. Vì đáp án có thể rất lớn, nên thay vào đó, hãy in ra số dư của đáp án khi chia ~10^9 + 7~.

Hai cách sử dụng câu thần chú "Khắc xuất, khắc xuất" là khác nhau, nếu như vị trí cắt cây tre ngàn đốt để tạo ra các cây tre nhỏ hơn là khác nhau.

Một xâu kí tự ~a~ được gọi là có thứ tự từ điển nhỏ hơn xâu kí tự ~b~ nếu một trong các điều sau thỏa mãn:

• ~a~ là tiền tố của ~b~, nhưng ~a \ne b~.

• tại vị trí đầu tiên mà xâu ~a~ và ~b~ khác nhau, xâu ~a~ có kí tự xuất hiện trước kí tự tương ứng ở xâu ~b~ trong bảng chữ cái tiếng Anh.

Input

Mỗi một test gồm nhiều test case khác nhau. Dòng đầu tiên của một test chứa số nguyên ~t~ (~t \le 2000~) là số lượng test case. Các test case được mô tả như sau.

Dòng đầu tiên và duy nhất của mỗi test case chứa xâu ~S~ (~1 \le |S| \le 2000~, ~S~ chỉ chứa các kí tự tiếng Anh in thường) là xâu biểu diễn của cây tre mà anh tiều phu cần phải mang về làng.

Dữ liệu đảm bảo tổng độ dài các cây tre của tất cả các test case trong một test không quá ~2000~.

Output

Với mỗi test case, hãy tìm số lượng cách sử dụng câu thần chú "Khắc xuất, khắc xuất" để cắt cây tre thành các cây tre bé hơn, sao cho sau khi gọi câu thần chú "Khắc nhập, khắc nhập", ta thu được cây tre được nối lại mà xâu biểu diễn của nó cũng là xâu ~S~. Vì đáp án có thể rất lớn, nên thay vào đó, hãy in ra số dư của đáp án khi chia ~10^9 + 7~.

Scoring

• Subtask 1, ứng với ~25~ điểm, các cây tre đã cho có độ dài không quá ~5~.

• Subtask 2, ứng với ~100~ điểm, tổng độ dài của các cây tre không quá ~100~.

• Subtask 3, ứng với ~234~ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán này có ~359~ điểm.

Sample Input 1

3
a
acb
ababa

Sample Output 1

0
2
3

Notes

Trong test case đầu tiên, cây tre đã cho được biểu diễn bởi xâu a. Cây tre này gồm có một đốt, nên không thể chia cây tre này thành các cây tre nhỏ hơn.

Trong test case thứ hai, cây tre đã cho được biểu diễn bởi xâu acb. Ta có hai cách gọi câu thần chú "Khắc xuất, khắc xuất" để chia cây tre như sau:

• Chia thành hai cây tre có biểu diễn là a và cb,

• Chia thành hai cây tre có biểu diễn là ac và b.

Ta không thể chia cây tre acb thành ba cây tre một đốt a, c và b, vì nếu chia như vậy, sau khi gọi câu thần chú "Khắc nhập, khắc nhập", cây tre thu được có biểu diễn là abc, khác với cây tre đã cho.

Trong test case thứ ba, cây tre đã cho được biểu diễn bởi xâu ababab. Ta có các cách sử dụng câu thần chú "Khắc xuất, khắc xuất" để chia cây tre như sau:

• a|baba,

• aba|ba,

• a|ba|ba.