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)~.

Cho một dãy số vô hạn các số nguyên được sắp xếp tăng dần, mỗi số chỉ chứa các chữ số ~4~ và ~7~. Hãy tìm số thứ ~N~ trong dãy. Sáu số đầu tiên trong dãy gồm: ~4~, ~7~, ~44~, ~47~, ~74~, ~77~. Dãy được đánh số thứ tự từ ~1~.

Dữ liệu:

• Dòng đầu tiên của đầu vào chứa số nguyên ~T (1 \le T \le 10^{5})~ 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 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 số thứ ~N (1 \le N \le 1000)~ trong dãy đã cho

Ví dụ:

Sample Input

5 
2
3
5
6
11

Sample Output

7
44
74
77
744

Trò chơi được mô tả như sau: Hai người chơi luân phiên, mỗi được nhận một con số tương ứng là ~X~ và ~Y~. Có ~N~ vòng chơi. Người có số ~X~ chơi trước. Tại mỗi vòng chơi, người chơi nhân gấp đôi con số của mình lên. Kết thúc vòng chơi, giả sử người có số ~X~ bây giờ có số ~W~, người có số ~Y~ bây giờ có số ~Z~. Bạn hãy cho biết thương nguyên của phép chia giữa ~max(W, Z)~ và ~min(W, Z)~.

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 ~3~ số nguyên ~X~, ~Y~, ~N~.

Kết quả:

• Ứng với mỗi bộ dữ liệu vào, chương trình của bạn cần in một dòng chứa một số nguyên là kết quả tương ứng.

Ràng buộc:

• ~1 \le T \lt 100; 1 \le X,Y,N \le 10^{9}~.

  Ví dụ:

Sample Input

2
1 2 1
3 2 3 

Sample Output

1
3

Cho bốn số nguyên ~L~, ~R~, ~a~, ~b~. Hãy đếm số lượng các bội số của ~a~ hoặc ~b~ có giá trị thuộc đoạn ~[L, R]~.

Dữ liệu:

Dòng đầu tiên của đầu 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 4 số nguyên ~L~, ~R~, ~a~, ~b~.

Kết quả:

Ứng với mỗi bộ dữ liệu đầu vào, in ra một số là đáp án bài toán trên một dòng.

Ràng buộc:

• ~1 \le T \le 100; 1 \le L \le R \le 10^{9}; 1 \le a, b \le 10^{4}~.

Ví dụ:

Sample Input

2
5 11 4 6 
3 1000 5 9 

Sample Output

2
289

Vào đầu của năm học mới tại trường học của các phù thủy, Hogwarts, các học sinh được ở trọ trong ký túc xá. Một trong những ký túc xá như vậy có một phòng kỳ diệu có kích thước ~a \times b \,(m^{2})~. Người quản lý muốn cho chính xác ~n~ học sinh ở phòng này. Nhưng quy định của trường yêu cầu rằng phải đảm bảo diện tích tối thiểu ~6~ (~m^{2}~) cho một học sinh trong một phòng (nghĩa là phòng dành cho ~n~ học sinh phải có diện tích ít nhất là ~6\times n~ (~m^{2}~). Người quản lý có thể phóng to bất kỳ chiều dài hoặc chiều rộng (hoặc có thể cả hai kích thước) của căn phòng lên một số nguyên dương tùy ý.

Bạn hãy giúp người quản lý thay đổi kích thước căn phòng để tất cả ~n~ sinh viên có ở trong đó và tổng diện tích của căn phòng là nhỏ nhất có thể.

Dữ liệu:

• Gồm một dòng chứa ba số nguyên cách nhau bởi dấu cách ~n~, ~a~ và ~b~, tương ứng là số lượng học sinh và kích thước của phòng.

Kết quả:

• In ra ba số nguyên ~s~, ~a_1~ và ~b_1~ (~a \le a_1, b \le b_1~) tương ứng là diện tích cuối cùng của căn phòng và kích thước của nó. Nếu có nhiều lời giải tối ưu, chỉ cần hãy in ra lời giải bất kì trong số đó.

Ràng buộc:

• ~1 \le n, a, b \le 10^{9}~.

Ví dụ:

Sample Input 1

3 3 5

Sample Output 1

18
3 6 

Sample Input 2

2 4 4 

Sample Output 2

16
4 4 

Tháp Giga là tòa nhà cao nhất và sâu nhất ở Cyberland. Tháp có ~17.777.777.777~ tầng, và được đánh số từ tầng ~-8.888.888.888~ đến tầng ~+8.888.888.888~ (các tầng được đánh số âm là các tầng nằm sâu dưới mặt đất). Đặc biệt, có tầng ~0~ ở giữa tầng ~-1~ và tầng ~1~. Mỗi ngày, hàng ngàn khách du lịch đến để tham quan tháp. Ở Cyberland, người ta tin rằng số "~8~" là con số may mắn (đó là lý do tại sao Tháp Giga có ~8.888.888.888~ tầng nổi trên mặt đất). Bên cạnh đó, một số nguyên được coi là số may mắn, khi và chỉ khi biểu diễn số thập phân của nó có chứa ít nhất một chữ số "~8~". Ví dụ: Các số ~8~, ~-180~, ~808~ đều là các số may mắn; còn các số ~42~, ~-10~ thì không phải.

Vova là khách du lịch đến thăm tháp để tìm sự may mắn. Bây giờ anh ta đang ở tầng ~A~. Anh ta muốn tìm một số nguyên dương ~B~ nhỏ nhất, sao cho nếu anh ta đi lên phía trên ~B~ tầng, anh ta sẽ gặp tầng có đánh số may mắn.

Dữ liệu:

• Gồm một dòng chứa một số nguyên ~A(|A| \le 10^{9})~.

Kết quả:

• In ra giá trị ~B~ nhỏ nhất thỏa mãn yêu cầu của Vova.

  Ví dụ:

Sample Input 1

179

Sample Output 1

1

Sample Input 2

-1

Sample Output 2

9

Sample Input 3

18

Sample Output 3

10

Giải thích:

• Ví dụ 1: Vova sẽ cần lên tầng ~180~.
• Ví dụ 2: Vova sẽ cần lên tầng ~8~.
• Ví dụ 3: Vova sẽ cần lên tầng ~8~.

Trên mặt phẳng tọa độ ~Oxy~, Rùa sống tại điểm có tọa độ ~(0, 0)~, Thỏ sống tại điểm có tọa độ ~(a, b)~. Hôm nay, Rùa nhận lời đến dự sinh nhật Thỏ. Rùa đi khá chậm, trong mỗi bước, Rùa chỉ có thể di chuyển ~1~ đơn vị độ dài theo một trong các hướng ngang hoặc dọc. Nói cách khác, từ vị trí ~(x, y)~, trong mỗi bước đi, Rùa chỉ có thể đi đến một trong các vị trí ~(x + 1, y)~, ~(x – 1, y)~, ~(x, y + 1)~ hoặc ~(x, y – 1)~. Rùa khá kém trong việc xác định hướng. Vì vậy, cậu ta chọn ngẫu nhiên hướng đi trong mỗi bước. Cậu ta có thể vô tình quay về nhà trong chuyến đi của mình, thậm chí có thể không biết rằng đã đến nhà Thỏ tại điểm ~(a, b)~ mà lại tiếp tục đi. May mắn là, cuối cùng Rùa đã đến được nhà Thỏ tại vị trí ~(a, b)~. Rùa nói với Thỏ: "Tớ đã phải mất đúng ~s~ bước để đi từ nhà tớ đến nhà bạn". Thỏ thì không chắc chắn về số bước đi mà Rùa đã nói. Hãy giúp Thỏ kiểm tra câu nói của Rùa về số bước đi từ nhà Rùa đến nhà Thỏ?

Dữ liệu:

• Gồm một dòng chứa ba số nguyên tố ~a~, ~b~ và ~s~.

Kết quả:

• Nếu bạn nghĩ Rùa đã nhầm và không thể thực hiện chính xác ~s~ bước đi từ nhà Rùa đến nhà Thỏ, thì hãy in ra từ "No". Ngược lại, hãy in ra từ "Yes".

Ràng buộc:

• ~-10^{9} \le a, b \le 10^{9}, 1 \le s \le 2\times10^{9}~.

Ví dụ:

Sample Input 1

5 5 11

Sample Output 1

No

Sample Input 2

10 15 25

Sample Output 2

Yes

Sample Input 3

0 5 1

Sample Output 3

No

Sample Input 4

0 0 2

Sample Output 4

Yes

Trên một đoạn vỉa hè đường phố, người ta lát ~N~ viên gạch, An có thể bước mỗi bước với khoảng cách ~1~ viên gạch hoặc ~2~ viên gạch. An muốn đi hết đoạn đường ~N~ viên gạch với số bước là bội số của ~M~ cho trước. Liệu An có thực hiện được điều đó không? Em hãy giúp An trả lời câu hỏi trên với số bước ít nhất hoặc cho biết là không thực hiện được điều đó.

Dữ liệu:

• Gồm hai số nguyên cách nhau bởi dấu cách ~N, M~.

Ràng buộc:

-~0 \lt N \le 10000; 1 \lt M \le 10~.

Kết quả:

• In một số nguyên thỏa mãn là bội số của ~M~ và là số bước tối thiểu mà An có thể thực hiện để đi hết đoạn đường lát ~N~ viên gạch. Nếu không có giá trị thỏa mãn điều kiện thi in ra số ~-1~.

Ví dụ:

Sample Input 1

10 2

Sample Output 1

6

Sample Input 2

3 5

Sample Output 2

-1

Giải thích:

• Ví dụ 1: An có thể đi trong ~6~ bước như sau: ~{2, 2, 2, 2, 1, 1}~.
• Ví dụ 2: Không có cách đi hợp lệ.

Giáo sư Vova chế tạo một robot mới. Trên mặt phẳng tọa độ Đề-các ~Oxy~, robot đang ở điểm xuất phát có tọa độ ~(x1, y1)~ và nó cần đi đến điểm đích có tọa độ ~( x2, y2)~. Trong mỗi bước đi, nếu robot đang ở điểm ~(x, y)~ thi nó có thể đến một trong các vị trí ~(x - 1, y - 1), (x-1,y),( x - 1, y + 1) , (x, y - 1 ) , (x, y + 1 ),(x+1,y-1) (x + 1, y) , (x + 1, y + 1)~ (tức là thay đổi giá trị hoành độ hoặc tung độ hoặc cả hai, bằng cách tăng hoặc giảm ~1~ đơn vị). Tìm số bước tối thiểu mà robot nên thực hiện để đến được vị trí đích.

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên ~x1, y1~ là vị trí xuất phát của robot;
• Dòng thứ hai chứa hai số nguyên ~x2, y2~ là vị trí đích của robot.

Ràng buộc:

• ~-10^{9} \le x1, y1, x2, y2 \le 10^{9}~.

Kết quả:

• Ghi ra số nguyên duy nhất ~d~ là số bước tối thiểu để robot đến được vị trí đích.

Ví dụ:

Sample Input 1

0 0
4 5

Sample Output 1

5

Sample Input 2

3 4
6 1

Sample Output 2

3

Giải thích:

• Trong test ví dụ ~1~: robot sẽ đi ~4~ bước theo chiều tăng cả hai hoành độ và tung độ, như vậy nó sẽ đến vị trí ~(4, 4)~. Sau đó, robot chỉ cần đi thêm ~1~ bước theo chiều tăng tung độ ~y~ và đến được vị trí đích.
• Trong test ví dụ ~2~: robot nên đi ~3~ bước theo chiều tăng hoành độ ~x~ và giảm tung độ ~y~.