[placeholder] rất lười vận động. Cậu suốt ngày ngồi ở nhà chơi điện tử. Một ngày, mẹ của [placeholder] rút dây máy tính, và bắt cậu ra ngoài đi dạo 1 vòng.

Nhà của [placeholder] nằm ở đỉnh ~1~ trong một đồ thị đầy đủ có hướng gồm ~n~ đỉnh. Các cạnh của đồ thị có trọng số. [placeholder] muốn tìm đi thăm ~k-1~ người bạn. Vì rất lười nên [placeholder] muốn chuyến đi dạo ngắn nhất có thể.

Bạn hãy giúp [placeholder] tìm một chu trình đơn giản có độ dài ~k~ có tổng trọng số các cạnh là nhỏ nhất.

Input

Dòng đầu tiên chứa 2 số ~n~, ~k~, số đỉnh của đồ thị và độ dài chu trình cần tìm (~n \le 50~, ~k \le min(n, 8), k~ chẵn).

~n~ dòng tiếp theo, mỗi dòng chứa ~n~ số ~a_{i,j}~, độ dài cạnh từ đỉnh ~i~ đến đỉnh ~j~ (~1 \le a_{i,j} \le 100000, a_{i,i} = 0~)

Output

Dòng đầu chứa số ~s~ - độ dài của chu trình ngắn nhất. Dòng tiếp theo chứa ~k~ số - các đỉnh trên chu trình. Đỉnh đầu tiên của chu trình phải là đỉnh ~1~.

Sample Input 1

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

Sample Output 1

11
1 2 3 5 

Trò chơi tháp Hà Nội là trò chơi nổi tiếng với những chiếc đĩa có kích thước đôi một khác nhau, có lỗ nằm ở giữa, nằm xuyên trên ba chiếc cọc A, B, C

Trò chơi bắt đầu bằng trạng thái các đĩa được chồng lên nhau ở cọc A, đĩa nhỏ nằm trên đĩa lớn, tức là đĩa nhỏ nhất được nằm trên cùng, tạo ra một dạng hình nón. Yêu cầu của trò chơi là chuyển toàn bộ số đĩa từ cọc A sang cọc C, tuân theo các quy tắc sau:

• Chỉ sử dụng 3 cọc để chuyển.

• Một lần chỉ được di chuyển một đĩa nằm trên cùng từ cọc này sang cọc khác.

• Một đĩa chỉ được đặt lên một đĩa lớn hơn.

Trong bài toán này, chúng ta sẽ có n chiếc đĩa, đánh số từ 1 đến n theo thứ tự kích thước đĩa tăng dần. Ban đầu, các đĩa nằm rải rác ở ba cọc nhưng vẫn thỏa mãn điều kiện đĩa nhỏ nằm trên đĩa lớn và mục tiêu là chuyển toàn bộ đĩa thành một chồng đĩa ở cọc C.

Yêu cầu: Cho trạng thái các đĩa nằm ở các cọc, hãy tìm cách chuyển toàn bộ đĩa thành một chồng đĩa ở cọc C.

Input

• Dòng đầu chứa số nguyên dương n.

• Dòng thứ hai chứa một xâu gồm ~n~ kí tự, kí tự thứ ~i~ ~(i = 1,2, ..., n)~ bằng 'A' hoặc 'B' hoặc 'C' cho biết đĩa thứ i nằm ở cọc A hay cọc B hay cọc C.

Output

• Dòng đầu chứa số nguyên ~s~ là số lần chuyển đĩa.

• Dòng thứ ~j~ ~(j = 1, 2, ..., s)~ trong ~s~ dòng tiếp theo, mỗi dòng gồm đúng hai kí tự mô tả một thao tác chuyển đĩa. Cụ thể, kí tự thứ nhất là tên cọc chứa đĩa cần chuyển, kí tự thứ hai là tên cọc mà đĩa chuyển tới.

Scoring

• Có 20% số test tương ứng với 20% số điểm bài có với ~n = 3~.

• Có 30% số test khác ứng với 30% số điểm của bài có ~n \le 10~ và cả ~n~ đĩa ban đầu ở cọc A.

• Có 20% số test khác ứng với 20% số điểm của bài có ~n \le 10~.

• Có 30% số test còn lại với 30% số điểm còn lại của bài có ~n \le 20~.

Sample Input 1

3
AAC

Sample Output 1

3
AB
AC
BC

Notes

Để chuẩn bị dọn vào ngôi nhà mới nhỏ nhỏ xinh xinh của mình tại chốn đồng quê bên bờ sông Hậu nên thơ hữu tình, Phúc cần phải chuẩn bị xây dựng một bể chứa nước để cung cấp nước sinh hoạt cho mọi công việc hằng ngày của mình. May mắn thay cho Phúc là ngôi nhà Phúc chuẩn bị dọn vào đã từng có người ở trước đó, nên ở đây đã có một bể chứa nước được xây từ trước nên Phúc không phải xây lại từ đầu. Tuy nhiên, để cuộc sống của mình có phần tiện nghi và thoải mái hơn, Phúc quyết định sẽ chi một khoản tiền nhỏ để nâng cấp bể nước hiện có.

Bể nước của người chủ cũ của căn nhà được cấu tạo từ ~n~ cột đá, với cột đá thứ ~i~ ~( 1 \le i \le n)~ có chiều cao là ~h_i~ ~(1 \le h_i \le 10^9)~. Khi đổ nước vào bể, nước ở trong bể sẽ được giữ lại khi ở bên trái và bên phải của bể có một cột đá khác có thể chặn lượng nước đó, nếu không thì nước sẽ trào ra ngoài bể.

Phúc có thể chi ra tối đa là ~k~ đồng để nâng cấp bể đá. Phúc có thể chi ~1~ đồng cho mỗi một viên đá có kích thước ~1 \times 1~ và đặt viên đá ấy ở trên cùng của một cột đá bất kì để nâng chiều cao của cột đá lên.

Vì Phúc không có nhiều tiền và cũng không giỏi tính toán nên Phúc cần phải rất thận trọng đối với cách nâng cấp để mình có được một cuộc sống tiện nghi nhất và dư dả nguồn nước nhất. Thế nên, mong các bạn có thể giúp Phúc nghĩ cách làm sao để chỉ với ~k~ đồng thôi mà vẫn có thể nâng cấp bể chứa để bể có thể chứa được nhiều nước nhất nhé!

Input

Dòng đầu tiên gồm ~2~ số nguyên dương ~n, k~ (~1 \le n, k \le 12~) - số cột đá của bể chứa nước và số tiền mà Phúc có.

Dòng tiếp theo gồm ~n~ số nguyên dương ~h_1, h_2,..., h_n~ (~1 \le h_i \le 10^9~, ~1 \le i \le n~) - độ cao ban đầu của mỗi cột đá của bể chứa nước.

Output

Gồm một dòng duy nhất chứa một số nguyên dương là lượng nước tối đa bể nước có thể chứa sau khi được Phúc tu sửa.

Sample Input 1

9 2
1 4 1 2 2 4 1 2 1

Sample Output 1

11

Notes

Hình sau minh họa ví dụ cho test mẫu (các ô màu vàng đại diện những viên đá Phúc chọn để đặt lên, và các ô màu xanh lá đại diện cho mực nước mới được thêm vào)

Minh họa cho một chiến thuật xây hồ nước tối ưu của Phúc

Bạn được nhận ~n~ xâu kí, mỗi xâu gồm các chữ cái tiếng Anh in thường. Cần chọn ra một số xâu trong ~n~ xâu đó sao cho khi ghép tất cả chúng lại, ta được một xâu mới bao gồm đầy đủ các kí tự trong bảng chữ cái tiếng Anh. Hãy đếm số cách để thực hiện yêu cầu trên. Hai cách được coi là khác nhau khi có một xâu được chọn ở cách này không được chọn trong cách kia.

Input

- Dòng đầu tiên gồm số nguyên dương ~n~ ~(n \le 25)~ miêu tả số lượng xâu.

- ~n~ dòng tiếp theo, mỗi dòng bao gồm một xâu kí tự ~S~ ~(|S| \le 30)~ gồm các chữ cái tiếng Anh in thường.

Output

- In ra một số nguyên là kết quả bài toán.

Sample Input 1

8
the
quick
brown
fox
jumps
over
lazy
dog

Sample Output 1

1

Sample Input 2

3
a
b
abcdefghijklmnopqrstuvwxyz

Sample Output 2

4

Notes

Cho dãy số gồm ~n~ phần tử và số nguyên ~m~. Nhiệm vụ của bạn là đếm số cách điền các dấu ~+~, ~-~ và ~*~ giữa các phần tử ~a_i~ và ~a_{i + 1}~ với ~i < n~ để tạo thành biểu thức có giá trị chia hết cho ~m~.

Input

Dòng đầu tiên chứa số nguyên ~t~ là số bộ test. Các dòng sau là ~t~ bộ test.

Mỗi bộ test bao gồm:

• Dòng đầu tiên chứa 2 số nguyên dương ~n~ và ~m~ (~2 \leq n \leq 10~, ~m \leq 10^9~).

• Dòng tiếp theo gồm ~n~ số nguyên là các phần tử của dãy ~a~ (~0 \leq a_i \leq 10^9~).

Output

Với mỗi bộ test, in ra số lượng biểu thức thỏa mãn.

Sample Input 1

1
4 2
5 5 5 9

Sample Output 1

14

Notes

Cho ba số nguyên ~n~, ~m~, ~x~. Bạn cần đếm số lượng dãy ~a_1, a_2, \dots, a_n~ thoả:

• Các phần tử ~a_i~ có giá trị thuộc ~[1, x]~.

• Dãy thoả ~m~ điều kiện được biểu diễn bởi bộ ba phần tử ~(i, j, g)~ cho biết ~GCD(a_i, a_j) = g~.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n~, ~m~, ~x~ (~3 \le n \le 9, 0 \le m \le n, 3 \le x \le 12~).

• ~m~ dòng tiếp theo, mỗi dòng gồm ba sốn nguyên dương ~i~, ~j~, ~g~ (~1 \le i, j \le n \; và \; i \ne j, 2 \le g \le x~).

Output

Một số nguyên duy nhất là số lượng dãy ~a_1, a_2, \dots, a_n~ thoả.

Scoring

• ~20\%~ test có ~n, m, x \le 7~.

• ~20\%~ test khác có ~|i - j| = 1~ với mọi truy vấn.

• ~60\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

2 1 5
1 2 3

Sample Output 1

1

Sample Input 2

3 2 6
1 2 3
3 1 2

Sample Output 2

2

[placeholder] rất thích chơi xếp hình. Bộ đồ chơi mới nhất của cậu là một tập các chữ số.

[placeholder] cũng rất thích số ~n~. Cực kỳ thích là đằng khác! [placeholder] thích ~n~ bằng cả trái tim!!!!

Trớ trêu thay, bộ đồ chơi của [placeholder] không thể xếp được thành ~n~! Do đó, [placeholder] quyết định sẽ sắp xếp các số đó thành tập các số có tích bằng ~n~. Tất cả các chữ số đều phải được sử dụng.

Input

Một duy nhất chứa số ~n~ (~n \le 10^9~) và một chuỗi các chữ số ~s~ (~|s| \le 1000~) - bộ đồ chơi của [placeholder]

Output

Dòng đầu chứa số ~k~ - số các số trong tập số xếp được. Dòng tiếp theo chứa ~k~ số có tích bằng ~n~. Các số không có chữ số ~0~ ở đầu.

Sample Input 1

69420 012347

Sample Output 1

2 20 3471

Siêu trộm marvinthang đang lên kế hoạch ăn trộm chiếc két sắt chứa chiếc cúp ~UEFA~ ~Champions~ ~League~ của ~PSG~ .

Khi đột nhập vào nơi chủ tịch ~Nasser~ ~Al~-~Khelaifi~ đang ở, marvinthang tìm thấy một tờ giấy ghi số ~n~ và dòng chữ ~numdiv~, nhờ trí thông minh của mình, cậu liền nhận ra mật khẩu két sắt là số lượng ước nguyên dương lớn nhất của một số nguyên dương nhỏ hơn hoặc bằng ~n~.

Vì không còn quá nhiều thời gian, mà số ~n~ lại quá lớn khiến marvinthang không thể tính toán đủ nhanh nên cậu quyết định đăng câu đố hóc búa này lên trên ~VNOJ~ để nhờ các thần đồng tin học giúp đỡ.

Các bạn hãy giúp marvinthang tìm đáp án nhé!!!

Input

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \leq t \leq 100~) - số lượng testcase.

~t~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ (~1 \leq n \leq 10^{18}~).

Output

Với mỗi testcase, in ra số lượng ước nguyên dương lớn nhất của một số nguyên dương nhỏ hơn hoặc bằng ~n~ trên một dòng.

Scoring

• Subtask ~1~ (~40\%~ số test): ~n \leq 10^7~.

• Subtask ~2~ (~60\%~ số test): không có ràng buộc gì thêm.

Sample Input 1

1
20

Sample Output 1

6

Vẫn là siêu trộm marvinthang, lần này cậu phải đối đầu với chiếc két sắt của ~Suzuki~ ~Jirokichi~ . Với sự giàu có của tập đoàn ~Suzuki~ , ông ~Jirokichi~ đã mua được một chiếc két sắt cực kì an toàn và khó mở.

Sau khi tiếp cận và điều tra, marvinthang biết được mã số của két sắt là một dãy nhị phân độ dài ~n~ (có ~n~ kí tự bao gồm ~0~ và ~1~). Cậu đã thử nhập ~m~ mã số, nhưng điều bất ngờ là sau mỗi lần nhập, hệ thống két sắt phản hồi lại và cho biết số lượng vị trí đúng của mã cậu vừa nhập (tức là số vị trí mà giá trị của mã vừa nhập và mã của két sắt giống nhau).

marvinthang đen đủi tới mức mà cậu không nhập nổi mã số nào có hơn ~5~ vị trí đúng. Bây giờ cậu hoàn toàn trở nên hoang mang, cậu nghi ngờ rằng đây chỉ là một trò lừa bịp~!?!!~.

Bạn hãy giúp marvinthang đếm số lượng mã số mà thỏa mãn các phản hồi của hệ thống.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ (~6\leq n \leq 35, 1\leq m \leq 10~) - lần lượt là độ dài của mã số và số lần thử của marvinthang.

~m~ dòng tiếp theo, mỗi dòng chứa ~s_i~ và ~c_i~ cách nhau bởi dấu cách tương ứng là mã số mà marvinthang đã nhập (gồm ~n~ kí tự ~0~ và ~1~) và phản hồi của hệ thống (~0 \leq c_i \leq 5~).

Output

In ra một số nguyên duy nhất là số lượng mã số thỏa mãn các phản hồi của hệ thống.

Sample Input 1

6 3
101010 2
111001 3
110110 3

Sample Output 1

5

Notes

Cho bảng hình chữ nhật gồm ~N~ hàng, ~M~ cột. Các ô trong bảng thuộc một trong hai trạng thái: rỗng hoặc không rỗng. Các ô rỗng chứa ký tự '.', các ô không rỗng chứa ký tự '#'.

Bạn được phép xếp các hình thuộc một trong hai dạng sau đây vào bảng:

Bạn cần kiểm tra xem có tồn tại một cách xếp sao cho mỗi ô rỗng thuộc đúng một hình và các ô không rỗng không thuộc hình nào. Lưu ý: Bạn không được xoay hay lật các hình được cho.

Input

Dòng đầu tiên gồm hai số nguyên dương ~N, M~ ~(2 \leq N, 2 \leq M, N*M \leq 16)~. ~N~ dòng tiếp theo, mỗi dòng gồm ~M~ ký tự thể hiện một hàng của bảng.

Output

In ra một dòng duy nhất gồm xâu ký tự "YES" nếu thực hiện được yêu cầu của đề bài, nếu không in ra "NO".

Sample Input 1

4 4
##.#
#..#
.#.#
....

Sample Output 1

YES

Sample Input 2

4 4
#..#
....
....
#..#

Sample Output 2

NO

Sample Input 3

4 4
#..#
...#
....
#..#

Sample Output 3

NO

Ban quản lý thành phố X quyết định phạt tiền bạn vì đỗ xe trái phép. Tuy nhiên vì ban quản lý đều rất tốt bụng, họ quyết định cho bạn chọn tiền phạt của chính mình. Thậm chí nếu tiền phạt là số âm, bạn sẽ được thưởng thêm tiền!

Bạn được cho số nguyên dương ~N~ và ~N~ số nguyên ~s_1, s_2, …, s_N~. Ban đầu các số ~s_i~ đều có giá trị là 1.

Mỗi lượt bạn được phép chọn một số ~s_i~ bất kỳ và đổi dấu số đó (1 thành -1, -1 thành 1).

Với mỗi số ~s_i~ ~(1 \leq i \leq N)~, bạn bị phạt lượng tiền là ~h_i*s_i~. Ngoài ra với mỗi cặp số ~s_i, s_j~ ~(1 \leq i < j \leq N)~, bạn bị phạt lượng tiền là ~w_{i, j} * s_i * s_j~.

Biết bạn có vô hạn lượt đổi dấu, tìm tổng tiền phạt nhỏ nhất bạn có thể thu được.

Input

Dòng đầu tiên gồm một số nguyên dương ~N~ ~(1 \leq N \leq 17)~. Dòng tiếp theo gồm ~N~ số nguyên ~h_1, h_2, ..., h_N~ ~(-10^6 \leq h_i \leq 10^6)~. ~N - 1~ dòng tiếp theo, dòng thứ ~i~ gồm ~N - i~ số nguyên ~w_{i, i + 1}, w_{i, i + 2}, ..., w_{i, N}~ ~(-10^6 \leq w_{i, j} \leq 10^6)~.

Output

Một số nguyên duy nhất là giá trị nhỏ nhất của biểu thức.

Sample Input 1

2
10 10
21

Sample Output 1

-21

Sample Input 2

3
-3 -2 1
3 -3
-3

Sample Output 2

-7

Sample Input 3

4
-2 5 3 4
-4 -4 0
0 2
3

Sample Output 3

-15

Notes