Cho N điểm có tọa độ nguyên dương. Hãy chọn một tam giác cân có hai cạnh nằm trên hai trục tọa độ sao cho chứa tất cả N điểm đã cho. In ra cạnh ngắn nhất của tam giác cân thỏa mãn.

Input

• Dòng đầu tiên chứa số nguyên dương ~T \le 100~ là số bộ test.
• Dòng tiếp theo chứa số nguyên dương ~N \le 10^4~ là số điểm trên mặt phẳng ~Oxy~.
• ~N~ dòng tiếp theo mỗi dòng chứa hai số nguyên dương ~x, y~ là tọa độ của các điểm. ~(x, y \le 10^3)~

Output:

• Gồm ~T~ dòng, tương ứng với mỗi bộ test, in ra kết quả của bài toán.

Sample Test

Input:

1
3
2 2
2 3
1 4

Output:

5

Cho hai dãy số gồm ~N~ phần tử ~A_1, A_2, ..., A_N~ và ~B_1, B_2, ..., B_N~. Dãy số ~C~ được tạo bởi lấy tổng hai phần tử bất kì của dãy số ~A~ và ~B~, cụ thể: ~C_i = A_j + B_k~, vậy dãy số ~C~ sẽ có ~N^2~ phần tử. Sắp xếp dãy ~C~ theo thứ tự không giảm. In ra ~K~ phần tử đầu tiên của dãy ~C~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ ~(N \le 10^5, K \le min(N^2, 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên mô tả dãy số ~A~. (~|A_i| \le 10^9~)
• Dòng thứ ba chứa ~N~ số nguyên mô tả dãy số ~B~. (~|B_i| \le 10^9~)

Output:

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

Sample Test

Input:

3 4
1 1 2
1 2 3

Output:

2 2 3 3

Cho một bảng số gồm ~N~ dòng, ~M~ cột. Giá trị của một dòng là giá trị tuyệt đối của tổng tất cả các số âm hoặc các số dương. Hãy tính tổng hai dòng có giá trị lớn nhất.

Input

• Dòng đầu tiên là hai số nguyên dương ~N, M \le 10^3~.
• ~N~ dòng tiếp theo mỗi dòng gồm ~M~ số nguyên mô tả bảng số. Các số có giá trị từ ~-10^9~ đến ~10^9~.

Output:

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

Sample Test

Input:

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

Output:

13

Giải thích

Chọn dòng ~1~ và dòng ~3~

Cho một số nguyên dương ~N~. Hãy đếm xem có bao nhiêu số nguyên dương ~X~ nhỏ hơn ~N~ thỏa mãn: ~X~ và ~N~ nguyên tố cùng nhau (tức là ~UCLN(X, N) =1~)

Input

• Dòng đầu tiên là số nguyên dương ~T \le 10~ là số lượng test.
• ~T~ dòng tiếp theo mỗi dòng chứa một số nguyên dương ~N \le 10^9~.

Output:

• ~T~ dòng mỗi dòng là một số nguyên duy nhất là kết quả của test tương ứng~.

Sample Test

Input:

2
7
10

Output:

6
4

Số nguyên dương ~N~ là chia hết cho ~9~ khi và chỉ khi tổng các chữ số của nó chia hết cho ~9~.

Yêu cầu: Cho số nguyên dương ~N~. Hãy đổi một chữ số trong ~𝑁~ sao cho số mới được tạo ra có giá trị nhỏ nhất và chia hết cho ~9~. Số mới được tạo ra có thể có chữ số ~0~ ở đầu tiên.

Dữ liệu nhập vào từ file văn bản CH9.INP:

• Dòng đầu tiên chứa ~T~ là số test dữ liệu của bài toán ~(T \le 15);~
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~N~.

Tổng số lượng chữ số ở mọi test không quá ~10^6~.

Kết quả ghi ra file văn bản CH9.OUT:

Gồm ~𝑇~ dòng, mỗi dòng chứa một số nguyên dương tương ứng là kết quả theo yêu cầu.

Ràng buộc:

• Có ~50\%~ số test tương ứng với ~50\%~ số điểm của bài thoả mãn: ~T=1;~
• ~50\%~ số test còn lại ứng với ~50\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

3
34125
5441
22221

Output

34128
0441
22221

Số nguyên dương ~d~ được gọi là ước của số nguyên dương ~N~ nếu ~N~ chia hết cho ~d~. Ví dụ: các ước của ~9~ là ~1, 3~ và ~9;~ các ước của ~10~ là ~1, 2, 5~ và ~10~.

Yêu cầu: Cho hai số nguyên dương ~L~ và ~R~ ~(L ≤ R)~. Hãy tính tổng của tất cả các số nguyên dương là ước của ít nhất một số trong đoạn từ ~L~ tới ~R~ ~(~bao gồm cả ~L~ và ~R)~.

Dữ liệu vào từ tệp văn bản SUMDIV.INP:

Gồm một dòng chứa hai số nguyên dương ~L~ và ~R~ ~(1 ≤ L ≤ R ≤ 10^9).~

Kết quả ghi ra tệp văn bản SUMDIV.OUT:

Một số nguyên duy nhất là tổng của tất cả các số nguyên dương là ước của ít nhất một số trong đoạn từ ~L~ tới ~R~.

Ràng buộc

• Có ~20\%~ số test ứng với ~R ≤ 1000~;
• ~25\%~ số test khác ứng với ~R - L ≤ 1000~;
• ~25\%~ số test khác ứng với ~R ≤ 10^6~;
• ~30\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

9 12

Output

63

Giải thích

Các số là ước của ít nhất một số trong đoạn ~[9, 12]~ là: ~1, 2, 3, 4, 5, 6, 9, 10, 11~ và ~12~ ~(7~ và ~8~ không nằm trong danh sách này vì cả ~9, 10, 11~ và ~12~ đều không chia hết cho ~7~ hoặc ~8)~.

Ta có ~1 + 2 + 3 + 4 + 5 + 6 + 9 + 10 + 11 + 12 = 63~.

Input

7 7

Output

8

Giải thích

Các số là ước của ~7~ là ~1~ và ~7~. Ta có ~1 + 7 = 8~.

Cô giáo làng Kamishirasawa Keine nhặt được một cuốn sách lạ, hóa ra đó là sách dạy lập trình ở thế giới bên ngoài. Cô định mang về dạy cho các bạn nhỏ nhưng vì sách toàn bài tập khó nên cả cô vẫn chưa giải được. Chính vì thế cô nhờ bạn giúp giải bài toán sau:

Với mỗi số từ ~1~ đến ~9~ cho ~p_i~ là số lần xuất hiện của chữ số ~i~. Hãy tính tổng của tất cả các số khác nhau được tạo bởi những chữ số đã cho.

Input

• Dòng đầu tiên là số nguyên dương ~T \le 5000~ là số lượng test.
• ~T~ dòng tiếp theo mỗi dòng gồm 9 số nguyên ~0 \le p_i \le 9~.

Output:

• ~T~ dòng mỗi dòng là một số nguyên duy nhất là tổng các số có thể tạo được modulo ~10^9+7~.

Sample Test

Input:

3
0 0 0 1 0 0 0 1 0
0 0 0 1 0 1 0 2 0
1 2 0 2 1 1 1 0 1 

Output:

144
95818
689045052

• Giải thích: Ở test đầu tiên các số tạo ra được là: ~4 + 8 + 48 + 84 = 144~