"TextFile" là một virus chuyên tấn công các file văn bản theo phương thức sau: Sao chép một đoạn các ký tự liên tiếp trong trong nội dung của file văn bản vào bộ nhớ trong, thay đổi một số ký tự trong đoạn này, sau đó chèn đoạn văn bản đã thay đổi vào ngay sau đoạn văn bản vừa sao chép trong file văn bản.

Vinh đang phát triển phần mềm để phát hiện một file văn bản đã bị nhiễm virus nói trên hay chưa. Vì thế, Vinh cần giải quyết bài toán sau: Cho xâu ký tự ~T~ và số nguyên không âm ~k~, xâu con gồm các ký tự từ vị trí ~p~ đến vị trí ~q~ của xâu ~T~ được gọi là đoạn có khả năng bị virus sao chép mức ~k~ nếu nó sai khác với xâu con gồm các ký tự từ vị trí ~q+1~ đến vị trí ~q+(q-p+1)~ của xâu ~T~ ở không quá ~k~ vị trí.

Ví dụ, xét xâu T = zabaaxy và ~k = 1~. Đoạn văn bản ab từ ký tự thứ ~2~ đến ký tự thứ ~3~ là đoạn văn bản độ dài ~2~ có khả năng bị virus sao chép mức ~1~ vì nó khác với đoạn văn bản aa gồm các ký tự từ ký tự thứ ~4~ đến ký tự thứ ~5~ của xâu ~T~ ở ~1~ vị trí.

Yêu cầu: Cho xâu ký tự ~T~ và ~n~ số nguyên không âm ~k_1, k_2, \ldots, k_n~. Với mỗi giá trị ~k_i~, hãy tìm độ dài đoạn dài nhất trong xâu ~T~ có khả năng bị virus sao chép ở mức ~k_i~ ~(i = 1, 2, \ldots, n)~.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(n \le 10)~.
• Dòng thứ hai chứa một xâu ~T~ gồm các chữ cái in thường lấy từ tập 26 chữ cái tiếng Anh từ a đến z.
• Dòng thứ ~i~ trong số ~n~ dòng tiếp theo ghi số nguyên không âm ~k_i~ ~(k \le 10, i = 1, 2, \ldots, n)~.

Output

Ghi ra ~n~ dòng, dòng thứ ~i~ ghi một số nguyên không âm là độ dài đoạn dài nhất có khả năng bị virus sao chép ở mức ~k_i~, ~i = 1, 2, \ldots, n~. Ghi ~0~ nếu không tìm được đoạn như vậy.

Giới hạn

Ký hiệu ~m~ là độ dài của xâu ~T~.

• Có ~40\%~ số lượng test thoả mãn điều kiện: ~m \le 300~;
• Có thêm ~30\%~ số lượng test thoả mãn điều kiện: ~m \le 3\,000; \; k_i = 0~ với mọi ~i~;
• ~30\%~ số lượng test còn lại thoả mãn điều kiện: ~m \le 3\,000~.

Sample Input 1

2
zabaaxy
0
1

Sample Output 1

1
2

Sample Input 2

2
zcaabcaaaa
0
1

Sample Output 2

2
4

Note

Giải thích: Trong test ví dụ 2, đoạn dài nhất có khả năng bị virus sao chép ở mức ~0~  là aa có độ dài ~2~, đoạn dài nhất có khả năng bị virus sao chép ở mức ~1~ là caab có độ dài ~4~.

Năm 1202, Leonardo Fibonacci, nhà toán học người Ý, tình cờ phát hiện ra tỉ lệ vàng 0.618 được tiệm cận bằng thương của hai số liên tiếp trong một loại dãy số vô hạn được một số nhà toán học Ấn Độ xét đến từ năm 1150. Sau đó dãy số này được đặt tên là dãy số Fibonacci ~{F_i: i = 1, 2, \ldots}~, trong đó ~F_1 = F_2 = 1~ và mỗi số tiếp theo trong dãy được tính bằng tổng của hai số ngay trước nó. Đây là 10 số đầu tiên của dãy Fibonacci: ~1, 1, 2, 3, 5, 8, 13, 21, 34, 55~. Người ta đã khám phá ra mối liên hệ chặt chẽ của số Fibonacci và tỉ lệ vàng với sự phát triển trong tự nhiên (cánh hoa, cành cây, vân gỗ), trong vũ trụ (hình xoáy trôn ốc dải ngân hà, khoảng cách giữa các hành tinh), hay sự cân đối của cơ thể con người. Đặc biệt số Fibonacci được ứng dụng mạnh mẽ trong kiến trúc (Kim tự tháp Ai Cập, tháp Eiffel), trong mỹ thuật (các bức tranh của Leonardo da Vinci), trong âm nhạc (các bản giao hưởng của Mozart) và trong nhiều lĩnh vực khoa học kĩ thuật.

Trong toán học, dãy Fibonacci là một đối tượng tổ hợp quan trọng có nhiều tính chất đẹp. Có nhiều phương pháp hiệu quả liệt kê và tính các số Fibonacci như phương pháp lặp hay phương pháp nhân ma trận.

Sau khi được học về dãy số Fibonacci, Sơn rất muốn phát hiện thêm những tính chất của dãy số này. Vì thế Sơn đặt ra bài toán sau đây: Hỏi rằng có thể tìm được một tập con các số trong ~n~ số Fibonacci liên tiếp bắt đầu từ số thứ ~i~, sao cho tổng của chúng chia hết cho một số nguyên dương ~k~ ~(k \le n)~ cho trước hay không? Nhắc lại, một tập con ~q~ số của một dãy ~n~ số là một cách chọn ra ~q~ số bất kỳ trong số ~n~ số của dãy đó, mỗi số được chọn không quá một lần.

Yêu cầu: Hãy giúp Sơn giải quyết bài toán đặt ra.

Input

• Dòng thứ nhất ghi số nguyên dương ~T~ ~(T \le 10)~ là số lượng bộ dữ liệu
• Mỗi dòng trong ~T~ dòng tiếp theo chứa ba số nguyên dương ~n~, ~i~ và ~k~ là thông tin của một bộ dữ liệu.

Các số trên cùng dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra ~T~ dòng tương ứng với kết quả của ~T~ bộ dữ liệu đầu vào, mỗi dòng có cấu trúc như sau: Đầu tiên ghi số nguyên ~q~ là số lượng các số trong tập con tìm được, tiếp đến ghi ~q~ số nguyên là các số thứ tự trong dãy Fibonacci của ~q~ số trong tập con tìm được. Nếu không tìm được tập con thoả mãn điều kiện đặt ra thì ghi ra một số ~0~.

Nếu có nhiều cách chọn thì chỉ cần đưa ra một cách chọn bất kỳ.

Giới hạn

• Có ~20\%~ số lượng test thoả mãn điều kiện: ~n \le 20, i \le 10^6~;
• Có ~20\%~ số lượng test khác thoả mãn điều kiện: ~n \le 10^3, i \le 10^6~;
• Có ~20\%~ số lượng test khác thoả mãn điều kiện: ~n \le 10^6, i \le 10^6~;
• Có ~10\%~ số lượng test khác thoả mãn điều kiện: ~n \le 20, i \le 10^{15}~;
• Có ~10\%~ số lượng test khác thoả mãn điều kiện: ~n \le 10^3, i \le 10^{15}~;
• ~20\%~ số lượng test còn lại thoả mãn điều kiện: ~n \le 10^6, i \le 10^{15}~.

Sample Input

1
10 3 9

Sample Output

4 3 4 5 6

Note

Giải thích: Trong test ví dụ, một tập con thoả mãn điều kiện đặt ra là tập gồm 4 số ~F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8~ với tổng bằng ~18~.

Sơn và Vinh là hai người bạn thân thiết vì cùng chung sở thích là tham gia vào các trò chơi trí tuệ. Sơn mới nghĩ ra một trò chơi mới để thách đố Vinh. Trò chơi được mô tả như sau: Trên mặt phẳng Sơn vẽ một bản đồ giao thông gồm ~n~ nút. Các nút được đánh số từ ~1~ đến ~n~. Giữa các nút có ~m~ đoạn đường cho phép đi theo cả hai chiều. Trên mỗi đoạn đường có đặt một số quả chuối. Vinh được phép xuất phát từ một nút tuỳ ý đi theo các đoạn đường nối giữa các nút rồi quay trở lại nút xuất phát. Trong quá trình di chuyển không được phép di chuyển qua cùng một đoạn đường nhiều hơn một lần. Giả sử số lượng chuối trên các đoạn đường mà Vinh chọn để di chuyển qua là ~s_1, s_2, \ldots, s_k~. Khi đó số điểm mà Vinh đạt được theo cách đi này là ~\min{(s_1, s_2, \ldots, s_k)} + \max{(s_1, s_2, \ldots, s_k)}~.

Yêu cầu: Hãy giúp Vinh tìm cách đi đạt được nhiều điểm nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ theo thứ tự là số lượng nút và số lượng đoạn đường giữa các nút trên bản đồ;
• Dòng thứ ~i~ trong số ~m~ dòng tiếp theo chứa ba số nguyên ~u_i~, ~v_i~, ~w_i~ ~(1 \le u_i, v_i \le n; \; u_i \ne v_i; \; 0 \le w_i \le 10^9)~, trong đó ~u_i, v_i~ là chỉ số của ~2~ điểm được nối với nhau bởi đoạn đường thứ ~i~ và ~w_i~ là số lượng quả chuối có trên đoạn đường này, ~i = 1, 2, \ldots, m~. Chú ý là có thể có nhiều hơn một đoạn đường nối cùng một cặp nút.

Các số trên cùng dòng được ghi cách nhau bởi dấu cách.

Output

Một số nguyên là điểm số lớn nhất có thể đạt được trong trò chơi. Hãy ghi ra ~0~, nếu trên bản đồ không có cách đi thoả mãn điều kiện đặt ra.

Giới hạn

• Có ~40\%~ số lượng test thoả mãn điều kiện: ~n \le 10, m \le 100~;
• Có thêm ~30\%~ số lượng test thoả mãn điều kiện: ~n, m \le 5\,000~;
• ~30\%~ số lượng test còn lại thoả mãn điều kiện: ~n, m \le 10^5~.

Sample Input 1

4 4
1 2 1
2 3 2
3 1 1
1 4 100

Sample Output 1

3

Sample Input 2

3 2
1 2 1
1 3 19

Sample Output 2

0

Sample Input 3

3 4
1 2 1
2 1 2
1 2 3
1 3 100

Sample Output 3

5

Note