Cho ~Q~ truy vấn, mỗi truy vấn gồm ~3~ số nguyên dương ~K~, ~X~, ~Y~. Tính chữ số thứ ~K~ sau dấu phẩy của số ~X/Y~ (Tất nhiên, nếu có ít hơn ~K~ chữ số sau dấu phẩy của số ~X/Y~, đáp án sẽ là ~0~).

Ví dụ:

• ~2/5 = 0.4~, vậy nên số thứ ~6~ sau dấu phẩy của ~2/5~ là ~0~.
• ~1234 / 2345 = 0.52622601279...~, vậy nên số thứ ~3~ sau dấu phẩy của ~1234/2345~ là ~6~.

Input

• Dòng đầu tiên nhập vào số ~Q~ ~(Q \leq 2 \times 10^5)~.
• ~Q~ dòng tiếp theo, mỗi dòng nhập vào ba số nguyên dương ~K~, ~X~, ~Y~ ~(K, X, Y \leq 10^9)~.

Output

• Gồm ~Q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Sample Input

6
1 1234 2345
2 1234 2345
3 1234 2345
4 1234 2345
5 1234 2345
6 1234 2345

Sample Output

5
2
6
2
2
6

Scoring

Một nhà triết gia lỗi lạc đã từng đặt câu hỏi: "Ligma là gì?".

Ngày nay, Ligma vẫn còn đang là một vấn đề nan giải, nhưng với kỹ thuật khoa học hiện đại của thế kỉ XXI, các nhà khoa học đã tìm ra được một số tính chất đặc trưng của số Ligma.

Số Ligma là số nguyên dương thỏa mãn ít nhất một trong các tính chất sau:

1. Tổng chữ số là một số nguyên tố.
2. Tổng của các chữ số ở vị trí chẵn là một số nguyên tố.
3. Tổng của các chữ số ở vị trí lẻ là một số nguyên tố.

Cho ~Q~ truy vấn, mỗi truy vấn cho một số nguyên dương ~K~, tìm số Ligma bé thứ ~K~.

Ví dụ

• Số ~14~ là một số Ligma (tổng của các chữ số là ~5~, thỏa mãn ~(1)~)
• Số ~69420~ là một số Ligma (tổng của các chữ số ở vị trí chẵn là ~9+2=11~, thỏa mãn ~(2)~)
• Số ~18274~ cũng là một số Ligma (tổng của các chữ số ở vị trí lẻ là ~1 + 2 + 4 = 7~, thỏa mãn ~(3)~)
• Số ~177013, 19, 48~ đều không phải là số Ligma.

Input

• Dòng đầu tiên nhập vào số ~Q~ ~(Q \leq 5 \times 10^5)~.
• ~Q~ dòng tiếp theo, mỗi dòng nhập vào số nguyên dương ~K~ ~(K \leq 10^{15})~.

Outpu

• Gồm ~Q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Sample Input

7
1
2
3
4
5
6
1000000000000000

Sample Output

2
3
5
7
11
12
1822532371972654

Scoring

Cho một đồ thị liên thông có số cạnh nhỏ hơn số đỉnh, đỉnh thứ ~x~ có độ tuyệt vời là một số nguyên không âm ~A_x~.

Định nghĩa độ tuyệt vời của một đường đi là tổng xor (Định nghĩa của XOR) của độ tuyệt vời của tất cả các đỉnh trên đường đi đó. Độ tuyệt vời của cặp đỉnh ~(u, v)~ là tích của độ tuyệt vời của tất cả các đường đi đơn từ ~u~ đến ~v~. Vì đồ thị là liên thông, nên luôn tồn tại ít nhất một con đường giữa cặp đỉnh ~(u, v)~. Ta cũng có thể dễ dàng chứng minh được rằng có hữu hạn đường đi đơn giữa một cặp đỉnh bất kì, nên độ tuyệt vời của một cặp đỉnh ~(u, v)~ luôn tính được.

Độ tuyệt vời của một đồ thị chính là độ tuyệt vời lớn nhất của một cặp đỉnh bất kì.

Tính độ tuyệt vời của đồ thị nêu trên, cũng như số lượng cặp ~(u, v)~ (~u \leq v~) có độ tuyệt vời đúng bằng độ tuyệt vời của đồ thị.

Ví dụ

Cho đồ thị có ~N = 3~, ~M = 3~, ~A = [1, 2, 4]~ và các cạnh nối như hình minh họa trên.

• Cặp ~(1, 1)~: Có một đường đi đơn từ ~1~ tới ~1~ là chính đỉnh ~1~. Vậy độ tuyệt vời của cặp ~(1, 1)~ là: ~1~.

• Cặp ~(2, 2)~: Có một đường đi đơn từ ~2~ tới ~2~ là chính đỉnh ~2~. Vậy độ tuyệt vời của cặp ~(2, 2)~ là: ~2~.

• Cặp ~(3, 3)~: Có một đường đi đơn từ ~3~ tới ~3~ là chính đỉnh ~3~. Vậy độ tuyệt vời của cặp ~(3, 3)~ là: ~4~.

• Cặp ~(1, 2)~: Có hai đường đi đơn từ ~1~ tới ~2~ là ~1~ → ~2~ và ~1~ → ~3~ → ~2~. Vậy độ tuyệt vời của cặp ~(1, 2)~ là: ~(A_1 \oplus A_2) \times (A_1 \oplus A_3 \oplus A_2) = 21~.

• Cặp ~(1, 3)~: Có hai đường đi đơn từ ~1~ tới ~3~ là ~1~ → ~3~ và ~1~ → ~2~ → ~3~. Vậy độ tuyệt vời của cặp ~(1, 3)~ là: ~(A_1 \oplus A_3) \times (A_1 \oplus A_2 \oplus A_3) = 35~.

• Cặp ~(2, 3)~: Có hai đường đi đơn từ ~2~ tới ~3~ là ~2~ → ~3~ và ~2~ → ~1~ → ~3~. Vậy độ tuyệt vời của cặp ~(2, 3)~ là: ~(A_2 \oplus A_3) \times (A_2 \oplus A_1 \oplus A_3) = 42~.

Như vậy, độ tuyệt vời của đồ thị là ~42~, và có một cặp có có độ tuyệt vời bằng ~42~ là ~(2, 3)~.

Input

• Dòng đầu tiên nhập vào hai số nguyên không âm ~N, M~ ~(M, N \leq 10^5)~, là số đỉnh và số cạnh của đồ thị.
• Dòng thứ hai gồm ~N~ số nguyên không âm ~A_1, A_2, ..., A_N~ ~(0 \leq A_i \leq 2^{30})~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ nhập vào hai số nguyên dương ~u_i~, ~v_i~, cho biết có một cạnh nối giữa hai đỉnh ~u_i~, ~v_i~ ~(1 \leq u_i, v_i \leq N)~.
• Dữ liệu đầu vào đảm bảo các cạnh nhập vào sẽ tạo thành một đồ thị liên thông.

Output

• In ra kết quả của bài toán trên

Sample Input

5 4
10 0 15 2 6
1 2
2 3
2 4
3 5

Sample Output

15 2

Giải thích test mẫu:

Hình minh họa cho test ví dụ ở phần Sample Input.

Hai cặp ~(2, 3)~ và ~(3, 3)~ có độ tuyệt vời là ~15~. Đây cũng chính là độ tuyệt vời của đồ thị.

Scoring

"I love Big Black Cock" - huynhchiton981

BBC vừa mới tải về một trò chơi điện tử: Big Black Cock (Con gà trống khổng lồ màu đen). Trò chơi như sau: không gian trò chơi là một lưới ô vuông hai chiều kéo dài đến vô tận cả về chiều âm lẫn chiều dương. Gọi ô ~(x, y)~ là giao của hàng thứ ~x~ và cột thứ ~y~ (~x~, ~y~ có thể âm).

Có ~n~ vật cản trên lưới tọa độ này. Người chơi có một con gà trống ở ô ~(0, 0)~. Gọi tọa độ hiện tại cua con gà trống là ~(x, y)~. Gà trống có thể thực hiện ~4~ thao tác:

1. Đi đến ô ~(x-1, y)~.
2. Đi đến ô ~(x+1, y)~.
3. Đi đến ô ~(x, y-1)~.
4. Đi đến ô ~(x, y+1)~.

Thao tác thứ ~k~ có chi phí thực hiện ~w_k~.

Tuy nhiên, đây không phải là một tựa game thông thường. Khi BBC thực hiện một thao tác, con gà trống sẽ đi theo hướng đó cho đến khi ô đứng trước ô của người chơi là một vật cản.

Dĩ nhiên, nếu không tồn tại vật cản khi người chơi thực hiện thao tác, con gà trống sẽ tiếp tục đi và đi, cho đến vô tận. Như vậy, có thể coi con gà đã chết và kết thúc trò chơi, BBC không muốn thế.

Ví dụ: người chơi đang ở ô ~(0, 0)~, và chỉ có một vật cản ở ô ~(6, 0)~. Khi đó, nếu BBC thực hiện thao tác ~(2)~, con gà trống sẽ đi theo hướng đó cho đến khi bị vật cản chặn đường, như vậy BBC sẽ ở ô ~(5, 0)~. Nhưng nếu cậu thực hiện thao tác ~(1)~, con gà trống sẽ chết và trò chơi sẽ kết thúc.

Có một chiếc chìa khóa ở ô ~(x_0, y_0)~, và người chơi có thể lấy chìa khóa bằng cách đi qua ô này. Nhiệm vụ của người chơi là bằng những thao tác trên, hãy di chuyển sao cho tổng chi phí thực hiện các thao tác để từ ~(0, 0)~ đến lấy chìa khóa là thấp nhất. Hơn nữa, nhân vật không được chết sau khi lấy chìa khóa. (Cũng giống như việc bạn chơi bi 8 vậy, lỡ chốt bi đen rồi thì không được chết cái)

Sau khi chơi một hồi, BBC nhận ra trò chơi quá khó. Là một hacker chuyên nghiệp. BBC quyết định lập trình nên một công cụ giải trò chơi này. Và cậu ấy đã làm được (OMG!!!!) BBC thử thách bạn viết công cụ giải trò chơi này giống như anh ấy. Vì game quá dễ, nên sẽ có ~Q~ trường hợp, trường hợp thử ~t~ yêu cầu bạn giải quyết bài toán trên nếu chìa khóa được đặt tại ~(x_t, y_t)~.

Ví dụ:

Đây là video minh họa cho cách chơi.

Input

• Dòng đầu tiên nhập vào số nguyên dương ~T~ (~T \leq 5~) là số lượng bộ dữ liệu.
• Dòng thứ hai nhập vào hai số nguyên dương ~N, Q~ ~(N, Q \leq 50000)~, là số lượng vật cản và số lượng trường hợp.
• Dòng thứ ba nhập vào ~4~ số nguyên dương ~w_1, w_2, w_3, w_4~ (~w_1, w_2, w_3, w_4 \leq 10~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ nhập vào hai số nguyên dương ~x_i, y_i~ (~|x_i|, |y_i| \leq 2500~) là tọa độ của vật cản thứ ~i~.
• ~Q~ dòng tiếp theo, dòng thứ ~t~ nhập vào hai số nguyên dương ~x_t, y_t~ (~|x_t|, |y_t| \leq 2500~) là tọa độ chìa khóa trong trường hợp thứ ~t~.
• Dữ liệu đầu vào đảm bảo tọa độ của các vật cản và chìa khóa là phân biệt và không tồn tại trường hợp chìa khóa trùng với vật cản, cũng như không có vật cản và chìa khóa nào có tọa độ ~(0, 0)~.

Output

• Với mỗi trường hợp, in ra tổng chi phí thực hiện thao tác thấp nhất để có thể lấy được chìa khóa. Nếu BBC không thể hoàn thành yêu cầu với chiếc bàn phím bị hỏng, hãy in ~-1~.

Sample Input

1
4 6
1 2 3 4
0 -5
-5 -4
-4 5
1 4
0 -2
-2 -4
-4 0
-2 4
0 2
-2 0

Sample Output

3
4
8
10
13
-1

Giải thích test mẫu:

Vị trí của ~N~ vật cản và ~Q~ chìa khóa trong test mẫu nhìn giống như thế này:

• Để giải trường hợp ~1~ (chìa khóa xanh dương), ta chỉ cần thực hiện thao tác ~(3)~. Tổng chi phí là ~3~.
• Để giải trường hợp ~2~ (chìa khóa xám), ta thực hiện lần lượt thao tác ~(3)~, ~(1)~. Tổng chi phí là ~4~.
• Không có cách nào để giải trường hợp ~6~.

Scoring