Cho một xâu ~S~, mỗi kí tự trong ~S~ là chữ cái Latin thường, và khi quy đổi những chữ cái này thành những thứ tự ASCII, và từ những thứ tự đó chuyển qua hệ nhị phân ta được một ma trận như sau:

• Số ~0~ là những ô không đi dược
• Số ~1~ là những ô đi được
• Kí tự ~\#~ biểu thị cho kết thúc một hàng trong ma trận

Yêu cầu: xác định độ dài hàng, cột và tỉ lệ của các ô đi được với các ô không đi được sau khi dựng được ma trận từ xâu ~S~

Input

• Dòng đầu tiên gồm số nguyên ~l~ là độ dài của xâu ~S~ ~(1 \leq l \leq 10^6)~
• Dòng thứ hai gồm duy nhất một xâu ~S~ gồm các kí tự là chữ cái Latin thường hoặc là kí tự ~\#~, luôn đảm bảo rằng dữ liệu được cho sẽ không có nhiều dấu ~\#~ liền kề nhau mà mỗi dấu ~\#~ trong xâu ~S~ sẽ được cách nhau ít nhất là ~1~ kí tự và sẽ luôn không tồn tại kí tự ~\#~ ở đầu và cuối của xâu ~S~

Output

• Dòng đầu tiên yêu cầu in ra số ~n~ và ~m~ lần lượt là số hàng và số cột của ma trận được tạo ra từ xâu ~S~
• Dòng thử hai yêu cầu in ra tỉ lệ của các ô đi được với các ô không đi được, đáp án được in ra đúng ~9~ chữ số sau dấu phẩy.

Sample Input

4
ab#a

Sample Output

2 7
0.750000000

Note

• Kí tự đầu tiên là ~a~ có mã ~ASCII~ là ~97~, đổi sang hệ nhị phân ta được ~1100001~
• Kí tự thứ hai là ~b~ có mã ~ASCII~ là ~98~, đổi sang hệ nhị phân ta được ~1100010~
• Kí tự thứ ba là ~\#~ biểu thị cho kết thúc một hàng
• Kí tự thứ tư là ~a~ có mã ~ASCII~ là ~97~, đổi sang hệ nhị phân ta được ~1100001~

Vậy tổng quát, ma trận sau khi đổi từ xâu ~S~ sang hệ nhị phân của ta là:

Số hàng của ta là ~n = 2~, số cột của ta là ~m = 7~ do ta sẽ lấy hàng có số ít phần tử liên tiếp nhất đầu tiên

Xét ma trận ~2 \times 7~ được khoanh trong hình, ta có:

Số ô đi được là ~6~ và số ô không đi được là ~8~, vậy tỉ lệ của số ô đi được và số ô không đi được là: ~\frac{6}{8} = 0.750000000~

Xuất phát là học sinh chuyên toán nên HienJeony chưa bao giờ thấy toán là khó. Trong một tiết học nọ cũng như bao tiết học khác, HienJeony không chú ý nghe giảng nên bị thầy mời trả lời một số câu hỏi vô cùng khó ở bài học mới như sau: Cho biểu thức có phép Logarit là ~log_a(b^x)~ với ~a~ là số nguyên tố, hãy biểu diễn kết quả của phép tính này dưới dạng thừa số nguyên tố.

Input

• Dòng đầu tiên gồm số nguyên dương ~t~ ~(1 \leq t \leq 50)~
• ~t~ tiếp theo, mỗi dòng chứa ~3~ số ~a, b, x~ ~(1 \leq a \leq 10^3, 1 \leq b \leq 10^{18}, 1 \leq x \leq 10^6, a \leq b)~

Output

Trong trường hợp không thể biểu diễn kết quả dưới dạng thừa số nguyên tố thì in ra ~-1~, ngược lại ta in như sau:

• Dòng đầu tiên là các số mũ khi biểu diễn kết quả phép tính dưới dạng thừa số nguyên tố
• Dòng thứ hai là các thừa số nguyên tố khi biểu diễn phép tính

Lưu ý: thứ tự in ra của các số thuộc dòng đầu tiên và dòng thứ hai phải được in sắp xếp tăng dần theo thừa số nguyên tố.

Sample Input

2
3 6 1
3 9 12

Sample Output

-1
3 1 
2 3 

Note

Ở test ví dụ thứ hai, thực hiện phép tính và biểu diễn kết quả dưới dạng thừa số nguyên tố thì ta có: ~log_3(9^{12}) = 24 = 2^3 \times 3^1~

Đại dịch vừa qua Egg ở nhà khá nhiều và trở nên càng ngày càng lười, thế nên các thành viên trong nhà vô cùng tích cực sai vặt Egg. Một hôm Egg được mẹ nhờ đi chợ, do vừa trải qua mùa dịch nên siêu thị có chương trình ưu đãi vô cùng hấp dẫn. Siêu thị hiện tại có ~n~ món đồ khuyến mãi được bày bán và cứ mua ~k~ món đồ ~(1 \leq k \leq n)~ thì bạn sẽ phải chỉ trả giá trị trung bình của cả ~k~ món đồ đó mà thôi, nói cách khác gọi danh sách các món đồ có giá tiền lần lượt là: ~a_1~, ~a_2~, ~a_3~, ~\dots~, ~a_k~ và bạn phải trả giá tiền là ~a_1 + a_2 + a_3 + \dots + a_k~ để được ~k~ món đồ đó thì giờ đây bạn chỉ cần phải trả giá tiền là ~\frac{a_1 + a_2 + a_3 + \dots + a_k}{k}~. Với khả năng săn sale Shopee thượng thừa trong mùa dịch nên Egg biết đây là cơ hội để mình mua những món đồ mình thích với giá tốt. Cầm trong tay số tiền là ~x~, và trong siêu thị có ~n~ món hàng với mỗi món hàng có giá niêm yết là ~a_i~ ~(1 \leq i \leq n)~. Hãy xác định giúp Egg xem có bao nhiêu cách chọn các món đồ sao cho giá tiền trung bình là ~x~.

Input

• Dòng đầu tiên gồm số nguyên ~n~ ~(n \leq 36)~ và số nguyên ~x~ ~(1 \leq x \leq 10^{12})~
• Dòng thứ hai gồm ~n~ số nguyên ~a_i~ ~(1 \leq a_i \leq 10^{12})~

Output

• Một dòng duy nhất là số cách chọn món đồ với giá tiền trung bình là ~x~

Sample Input

4 5
4 4 6 6

Sample Output

5

Subtask

• ~60\%~ số test có ~1 \leq n \leq 10~
• ~40\%~ số test tiếp theo không có điều kiện gì thêm.

Nhân ngày sinh nhật, Minh được bố mẹ thưởng cho một chiếc bánh sinh nhật có dạng hình hộp chữ nhật và có ~k~ tầng kem, mỗi tầng kem này được tạo bởi các ô kem nhỏ hơn có hình lập phương ~1 \times 1 \times 1~ xếp lại với nhau, như thế luôn đảm bảo rằng ở tầng kem bất kỳ sẽ luôn có chiều dài là ~n~, chiều rộng là ~m~ và chiều cao luôn là ~1~. Là một người rất sành ăn nên Minh biết độ ngon của từng ô kem lập phương này nên nếu coi một tầng kem là một bảng hình chữ nhật thì độ ngon của ô kem lập phương thuộc hàng ~i~, cột ~j~ và tầng kem thứ ~z~ có giá trị là ~a_{i,j,z}~ . Khổ nỗi bánh kem thì rất to, mà bạn đến dự sinh nhật thì ít nên để làm cho buổi sinh nhật thêm "mặn mà" hơn, thay vì rảc muối lên chiếc bánh sinh nhật thì Minh quyết định trổ tài cắt chiếc bánh của mình từ hình hộp chữ nhật thành hình kim tự tháp có chiều rộng mặt đáy là ~X~, chiều dài mặt đáy là ~Y~ và có độ cao là ~Z~, khi bắt đầu cắt bánh, Minh quyết định cắt ở ô kem trái trên của mặt đáy có tọa độ là ~(x,y,g)~. Do là người rất cẩn thận nên trước khi cắt bánh, Minh muốn khảo sát với nhiều câu hỏi để nếu cắt bánh từ hình hộp chữ nhật thành kim tự tháp có chiều rộng mặt đáy là ~X~, chiều dài mặt đáy là ~Y~ và độ cao là ~Z~ thì Minh sẽ được tổng giá trị độ ngon là bao nhiêu, biết rằng kim tự tháp mà Minh muốn cắt là kim tự tháp có nhiều tầng với tầng trên luôn nhỏ hơn tầng dưới được minh họa như sau:

Input

• Dòng đầu tiên là ~3~ số ~n~, ~m~, ~k~ lần lượt là chiều dài ~n~, chiều rộng ~m~ và có ~k~ tầng kem của chiếc bánh sinh nhật ~(1 \leq n \times m \times k \leq 5 \times 10^5)~
• ~k~ khối dòng tiếp theo, khối dòng thứ ~t~ ~(1 \leq t \leq k)~ có ~n~ dòng, và ~m~ cột. Dòng thứ ~i~ ~(1 \leq i \leq n)~ thuộc khối dòng thứ ~t~ có ~m~ số nguyên là độ ngon của các ô kem có hình lập phương ~1 \times 1 \times 1~ và ô kem thứ ~j~ ~(1 \leq j \leq m)~ có giá trị độ ngon là ~a_{i,j,t}~ ~(1 \leq a_{i,j,t} \leq 10^6)~, với mỗi khối dòng như vậy được quy ước là một tầng kem của hình hộp chứ nhật
• Dòng tiếp theo chứa số nguyên dương ~Q~ ~(1 \leq Q \leq 10^5)~ là số câu hỏi của Minh
• ~Q~ dòng tiếp theo, mỗi dòng là ~6~ số nguyên dương ~X, Y, Z, x, y, g~ ~(1 \leq X, Y, Z \leq 10^6; 0 \leq x, y, g \leq 10^5)~

Output

• In ra ~Q~ dòng mỗi dòng là độ ngon của kim tự tháp với ~X, Y, Z, x, y, g~ tương ứng, nếu không tính được thì in ra ~-1~

Sample Input

4 4 2
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 
4 4 2 1 1 1

Sample Output

20

Subtask

• ~30\%~ số test có ~n \times m \times k \leq 100~
• ~70\%~ số test còn lại không có điều kiện gì thêm

Note

Quy ước tầng thứ ~1~ là đáy của hình hộp chữ nhật cũng như là đáy của hình kim tự tháp

Tại tầng thứ ~1~, ta chọn cắt từ ô kem hình lập phương có tọa độ là ~(1,1,1)~ đến hết lớp kem của tầng ~1~ vì ta quyết định không cắt ô kem nào ở ngoài biên cả, ta được kết quả là ~ans_1 = 16~

Tại tầng thứ ~2~, ta chọn cắt từ ô kem hình lập phương có tọa độ là ~(2,2,2)~ đến hết lớp kem của tầng ~2~ thỏa mãn chỉ cắt bỏ ô biên bên ngoài vào ~1~ ô, tức tầng kem bị cắt bỏ ~12~ ô kem để được ~4~ ô kem còn lại, ta được kết quả là ~ans_2 = 4~

Vậy tổng cộng độ ngon của kim tự tháp sẽ là ~ans_1 + ans_2 = 20~

Quá trình cắt bánh được mô tả như sau:

Sau những ngày học tập mệt mỏi, Copium thường tự thưởng cho mình đi chơi ở Escape Room - nổi tiếng với những màn phòng giải đố vô cùng hấp dẫn ở Việt Nam. Vốn là một người trên thông thiên văn, dưới tường địa lý nên Copium chọn cho mình phòng chơi khó nhất. Sau một hồi quan sát, Copium dùng một miếng giấy để vẽ lại bản đồ của căn phòng dưới dạng bảng gồm ~n~ dòng ~m~ cột, các dòng được đánh số ~x~ đến ~x+n-1~ từ trên xuống dưới và các cột được đánh số ~x~ đến ~x+m-1~ từ trái qua phải, gọi ô ~(i, j)~ là ô nằm trên dòng thứ ~i~ và cột thứ ~j~ của bảng. Copium hiện đứng ở ô ~(x, x)~ của bảng và cần đi chuyển đến ô ~(x+n-1, x+m-1)~. Nhiệm vụ chính để vượt qua căn phòng này là Copium phải xác định quãng đường ngắn nhất mỗi bước mà anh đó sẽ chỉ đi sang ô bên phải hoặc bên dưới. Biết mọi ô ~(i, j)~ đều có giá trị là ~i \times j~ và độ chính xác của một con đường được tính bằng ước chung lớn nhất của các giá trị các ô nằm trên con đường đó. Hãy giúp Copium xác định tổng độ chính xác của mọi con đường có thể để anh có thể vượt qua căn phòng.

Input

• Dòng đầu tiên chứa số nguyên ~t~ là số bản đồ của căn phòng mà Copium định vẽ ~ ( 1 \leq t \leq 1000 )~
• ~t~ dòng sau, mỗi dòng gồm ~3~ số nguyên lần lượt là ~x~, ~n~, ~m~ ~(1 \leq x \leq 10^{18}, 1 \leq n, m \leq 5 \times 10^ 5)~

Output

• In ra ~t~ dòng, ứng với mỗi dòng là tổng độ chính xác của mọi con đường, vì đáp án có thể là số rất lớn nên được chia lấy dư cho ~10^9+7~

Sample Input #1

1
2 2 3

Sample Output #1

4

Sample Input #2

2
1 5 5
4 3 5

Sample Output #2

70
20

Subtask

• ~20\%~ số test có ~x = 1~
• ~30\%~ số test tiếp theo có ~t \leq 5~
• ~50\%~ số test còn lại không có ràng buộc gì thêm.

Note

Ở sample test đầu tiên được giải thích như sau: