Có ~N~ con chuột ở trong một đường hầm thẳng hẹp, chỉ cho phép ~1~ con chuột ở một chỗ tại một thời điểm, có ~N~ cái tổ chuột nằm dọc theo đường hầm, mỗi cái tổ chỉ chứa vừa một con chuột. Một con chuột có thể ở nguyên vị trí của nó, hoặc di chuyển một bước sang phải từ vị trí ~x~ sang ~x+1~ hoặc di chuyển một bước sang trái từ ~x~ đến ~x-1~. Một bước di chuyển tiêu tốn ~1~ phút. Giả sử đường hầm là trục số nguyên ~Ox~, biết vị trí ~N~ con chuột và ~N~ tổ chuột, hãy tính số phút tối thiểu để con chuột cuối cùng chui được vào tổ.

Dữ liệu:

• Dòng đầu tiên của đầu vào chứa số nguyên ~T~ là số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm:
  • Dòng đầu chứa số nguyên ~N~.
  • Dòng thứ ~2~ chứa ~N~ số nguyên khác nhau cho biết vị trí của ~N~ con chuột.
  • Dòng thứ ~3~ chứa ~N~ số nguyên khác nhau cho biết vị trí của ~N~ tổ chuột.

Kết quả:

• Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra một dòng chứa số phút tối thiểu để con chuột cuối cùng chui được vào tổ.

Ràng buộc

• ~1 \leq T \leq 100 ; 1 \leq N \leq 10^4~.
• Vị trí của các con chuột và tổ chuột là số nguyên có giá trị tuyệt đối không quá ~10^7~.

Sample Input

1
3
4 -4 2
4 0 5

Sample Input

4

Mèo Tom và chuột Jerry đang chơi một trò chơi để phân định, ai thắng sẽ được lấy miếng phô mai cuối cùng trong tủ lạnh. Trò chơi như sau: Cho một số nguyên dương ~N~, hai người chơi luân phiên. Tom chơi trước, ai tới lần chơi, sẽ phải tìm một số nguyên ~a(a \lt N)~ là ước của ~N~, sau đó ~N~ sẽ bị trừ đi ~a~. Ai không tìm được số ~a~ nữa sẽ là người thua cuộc. Cho biết số ~N~, bạn hãy xác định Tom hay Jerry thắng.

Dữ liệu:

• Dòng đầu tiên của đầu vào chứa số nguyên ~T~ cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa số nguyên ~N~.

Kết quả:

• Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra một dòng chứa số ~1~ nếu Tom thắng hoặc số ~0~ nếu Jerry thắng.

Ràng buộc

• ~1 \leq T \leq 100 ; 1 \leq N \leq 10^6~.

Ví dụ:

Sample Input

2
2
4

Sample Input

1
1

Cho số nguyên ~N~. Hãy thực hiện lặp lại một số lần thao tác sau cho đến khi thu được số ~N~ có ~1~ chữ số. Cụ thể thao tác là: Thay ~N~ bằng tổng các chữ số của ~N~.

Dữ liệu:

• Dòng đầu tiên của đầu vào chứa số nguyên ~T~ cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa số nguyên ~N~.

Kết quả:

• Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra một dòng chứa số ~N~ cuối cùng.

Ràng buộc:

• ~1 \leq T \leq 100 ; 1 \leq N \leq 10^9~.

Ví dụ:

Sample Input

2
1
98

Sample Input

1
8

Cho số nguyên ~N~, và một số nguyên tố ~p~ tìm lũy thừa lớn nhất của ~p~ mà là ước của ~N~ ! ( ~N~ ! tức là ~N~ giai thừa).

Dữ liệu:

• Dòng đầu tiên của đầu vào chứa số nguyên ~T~ cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa hai số nguyên ~N~ và ~p~.

Kết quả:

• Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra một dòng số mũ lớn nhất của lũy thừa cơ số ~p~ mà là ước của ~N!~.

Ràng buộc:

• ~1 \leq T \leq 100 ; 1 \leq N \leq 10^5 ; 2 \leq p \leq 10^5~.

Ví dụ:

Sample Input

3
62 7
76 2
3 5

Sample Input

9
73
0

Hôm nay trên tập sân bóng, có hai tiền đạo Văn Toàn, Văn Quyết và thủ môn Văn Lâm. Với tư cách là huấn luyện viên, bạn tổ chức một buổi tập sút luân lưu để cải thiện hiệu suất của các tiền đạo. Nhiệm vụ của bạn là tìm ra được tiền đạo ghi bàn nhiều hơn giữa Văn Toàn và Văn Quyết. Giả sử, năng lượng ban đầu của Văn Toàn, Văn Quyết và Văn Lâm được ký hiệu lần lượt là ~T~, ~Q~ và ~L~. Với mỗi bàn thắng, năng lượng của người sút sẽ giảm đi ~1~ và sau mỗi lần bắt được bóng, năng lượng của thủ môn sẽ giảm đi ~1~. Tiền đạo có thể ghi bàn nếu năng lượng của thủ môn là ước số của năng lượng của anh ta. Buổi tập kết thúc khi năng lượng của thủ môn còn bằng ~1~. Giả sử cùng một người chơi có thể cố gắng ghi bàn nhiều lần và cả hai đều cố gắng tăng số lượng bàn thắng. Văn Toàn là một cầu thủ giỏi và luôn được ưu tiên trong đá phạt.

Dữ liệu:

• Dòng đầu tiên của đầu vào chứa số nguyên ~TC~ cho biết bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa ba số nguyên ~T~, ~Q~, ~L~.

Kết quả:

• Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra một dòng chứa số bàn thắng tương ứng của Văn Toàn và Văn Quyết.

Ràng buộc:

• ~1 \le TC \le 50; 1 \le T,Q,L \le 10^{5}~.

Ví dụ:

Sample Input

2
4 9 5
13 10 7

Sample Output

3 2 
0 3 

Giải thích:

Test 1:

• Lượt 1: ~L = 5~ không là ước của ~T = 4~ và ~Q = 9~ → không có bản thắng, năng lượng còn lại là: ~T = 4~, ~Q =9~, ~L = 4~ (thủ môn bị giảm ~1~ nămg lượng).

• Lượt 2: Văn Toàn ghi bản thứ ~1~ vì ~L~ là ước của ~T~. Năng lượng còn lại là: ~T = 3~, ~Q = 9~, ~L = 4~.

• Lượt 3: ~L = 4~ không là ước của ~T = 3~ và ~Q = 9~ → không có bàn thắng. Các năng lượng còn lại là: ~T = 3~, ~Q = 9~, ~L = 3~.

• Lượt 4: ~L~ là ước của cả ~T~ và ~Q~, nhưng do Văn Toàn được ưu tiên nên anh ta lại ghi tiếp bàn thứ 2. Các năng lượng còn lại là: ~T = 2~, ~Q = 9~, ~L = 3~.

• Lượt 5: ~L~ là ước của ~Q~, nên Văn Quyết ghi bàn thứ ~1~. Các năng lượng còn lại là: ~T = 2~, ~Q = 8~, ~L = 3~.

• Lượt 6: Không có bàn thắng nào được ghi vì ~L = 3~ không là ước của ~T = 2~ và ~Q = 8~. Các năng lượng còn lại là: ~T = 2~, ~Q =8~, ~L = 2~.

• Lượt 7: ~L = 2~ là ước của cả ~T = 2~ và ~Q = 8~. Văn Toàn lại được ưu tiên và ghi bàn thứ 3. Các năng lượng còn lại là ~T = 1~, ~Q = 8~, ~L = 2~.

• Lượt 8: ~L = 2~ là ước của ~Q = 8~, Văn Quyết ghi bàn thứ 2. Các năng lượng còn lại là: ~T = 1~, ~Q = 7~, ~L = 2~.

• Lượt 9: không ai ghi bàn vì ~L = 2~ không là ước của ~T = 1~, ~Q = 7~. Các năng lượng còn lại là ~T = 1~, ~Q = 7~, ~L = 1~. Trận đấu dừng.

Test 2:

• Vì ~T = 13~ là số nguyên tố nên Văn Toàn không ghi được bàn thắng nào, chỉ có Văn Quyết ghi được ~3~ bàn.

Cho một số nguyên dương ~K~. Nhiệm vụ của bạn là tìm các số lượng các cặp số nguyên dương ~(a; b)~, trong đó ~1 \le a \lt b \lt K~ và ~a + b \le K~.

Dữ liệu:

• Dòng đầu tiên của đầu vào chứa số nguyên ~T~ cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa số nguyên ~K~.

Kết quả:

• Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra một dòng chứa cặp số tìm được.

Ràng buộc:

• ~1 \le T \le 100; 1\le K \le 10^{5}~.

Ví dụ:

Sample Input

3 
2
4
5

Sample Output

0
2
4

Giải thích:

• ~K = 2~, không có cặp số ~(a; b)~ nào thỏa mãn.
• ~K = 4~, có cặp ~(1; 2), (1; 3)~.
• ~K = 5~, có ~3~ cặp ~(1; 2), (1; 3), (1; 4), (2; 3)~.