Trong lúc thưởng thức những miếng bánh trung thu bên tách trà đậm vị, thầy Hưng và thầy Bính đã cùng thảo luận về đam mê của mình là bộ môn số học. Những con số luôn có sức hút kỳ lạ và có thể giúp những người bận rộn nhất ngồi đàm đạo hàng giờ cùng nhau. Thầy Bính bèn ra một đề bài để thử thách đồng nghiệp của mình như sau: ban đầu, thầy Hưng được cho hai số ~1~ và thầy được thực hiện một hoặc nhiều thao tác

Mỗi thao tác, thầy Hưng được phép chọn một số nguyên dương ~k~ nào đó và nhân ~k~ vào một trong hai số, số còn lại thì nhân thêm ~k^2~. Chú ý rằng lựa chọn này là độc lập giữa các lần, tức là lần trước chọn số này, lần sau có thể chọn số khác đều được.

Thầy Bính đặt vấn đề là liệu rằng có thể tạo ra được hai số nguyên dương ~a, b~ từ các phép biến đổi trên hay không? Bạn hãy cùng thầy Hưng hoàn thành thử thách này nhé; nếu trả lời đúng, biết đâu sẽ được tặng những cái bánh ngon bổ dưỡng còn sót lại của mùa trung thu này đấy.

Input

Dòng đầu tiên là số lượng trường hợp ~T~ với ~1 \le T\le 35000~. Trong ~T~ dòng tiếp theo, mỗi dòng sẽ bao gồm hai số ~1 \le a, b \le 10^9~.

Output

Ứng với mỗi trường hợp, ghi Yes nếu có thể tạo được cặp số ~a~ và ~b~ nhờ các thao tác. Ngược lại thì ghi ra No.

Sample input

4 
2 4
75 45
16 16
8 8

Sample output

Yes
Yes
No
Yes

Giải thích

Ở cặp số ~(2,4)~, ta có thể chọn ~k=2~ và nhân ~(k,k^2)~ vào cặp ~(1,1)~ để thu được ~(2,4).~ Nếu ta chọn tiếp ~k=4~ và nhân ~(k^2,k)~ vào thì được cặp ~(8,8)~ như ở ví dụ cuối.

Ở cặp số ~(75,45)~, lần 1 ta chọn ~k=5~ và nhân ~(k^2,k)~ vào cặp ~(1,1)~ để được ~(25,5);~ tiếp tục chọn ~k=3~ và nhân ~(k,k^2)~ vào để được ~(75,45).~

Ta có thể chứng minh được không có cách nào để tạo ra cặp ~(16,16).~

Subtasks

• Subtask 1 (~70\%~ số điểm): ~T \le 10^3~ và ~a, b \le 10^5~
• Subtask 2 (~30\%~ số điểm): không giới hạn gì thêm.

Cho số nguyên dương ~n~ có tập hợp các ước nguyên tố là ~A~, hỏi có bao nhiêu số chính phương không vượt quá ~n~ mà tập ước nguyên tố của nó là tập con của ~A~?

Input

Số nguyên dương ~n~ với ~1 \le n \le 10^{14}.~

Output

Số lượng cần tìm.

Sample input

36

Sample output

5

Giải thích: các số thỏa mãn là ~1, 4, 9, 16, 36~.

Giai thừa ~n! = 1.2.3...n~ là một phép tính thú vị mà không có cách nào tính ra giá trị của nó nhanh hơn một vòng lặp for. Đó là một trong những bài học vở lòng khi coder Đức Tài học được trên kênh dạy lập trình TL channel. Sau khi kết thúc buổi học, em Tài đã được anh admin của kênh giới thiệu 2 bài tập nhẹ nhàng như sau: với ~x~ là số nguyên dương, ký hiệu ~f(x) = 1!.2! ... x!~ là tích các giai thừa từ ~1!~ đến ~x!~. Bây giờ cho trước số nguyên dương ~n~, hãy trả lời cho các câu hỏi sau:

1. Số nguyên dương ~k~ nhỏ nhất sao cho ~f(k)~ chia hết cho ~n~.

2. Số nguyên dương ~k~ nhỏ nhất sao cho ~f(n)~ không chia hết cho ~k~.

Bạn Tài có thể giải bài toán với ~n \le 10~, nhưng kênh TL lại cho giới hạn lên đến ~10^{12}~ và cho đến ~100~ test cases, SOS, hãy giúp Tài nhé.

Input

Dòng đầu tiên gồm số nguyên dương ~t \le 100~ cho biết số test.

Mỗi dòng tiếp theo trong ~t~ dòng gồm một số nguyên dương duy nhất với ~1 \le n \le 10^{12}.~

Output

Ứng với mỗi dòng, hãy trả lời cho câu hỏi 1) và 2).

Sample input

1
3

Sample output

3 5

Giải thích: ta thấy ~f(1)=1, f(2)=2~ chưa đủ chia hết cho ~3~, còn ~f(3)=1.2.6 = 12~ thì chia hết cho ~3~ nên đáp số của câu hỏi thứ nhất là ~3~; còn với câu hỏi thứ hai, ta thấy ~f(3)=12~ vẫn chia hết cho ~4~ nhưng không chia hết cho ~5~ nên đáp số là ~5.~

Các subtask trong bài (đều có chung giới hạn ~t \le 100~):

• Subtask 1: 10% điểm ứng với ~n \le 10~.

• Subtask 2: 30% điểm ứng với ~10 < n \le 2023.~

• Subtask 3: 30% điểm ứng với ~2023 < n \le 10^7.~

• Subtask 4: 30% điểm ứng với ~10^7 < n \le 10^{12}.~

Trong một lần đi dạo chơi quanh trường THPT chuyên Lê Hồng Phong rộng lớn thì Informath, con robot thích Toán nhưng yêu lập trình, đã vô tình lạc vào tòa nhà thư viện. Quá choáng ngợp với sự đồ sộ của nơi này, robot đã muốn tìm học hết các sách vở ở trong đó. Kho tàng tri thức trong thư viện không chỉ có sách in mà còn có một số tài liệu quý được số hóa thành ~T~ tập tin. Mỗi tập tin có kích thước không quá ~{{10}^{9}}~ kilobyte và robot sẽ lần lượt đọc chúng. Bộ xử lý của robot được thiết kế rất đặc biệt. Với mỗi tập tin, nó không đọc dữ liệu theo từng kilobyte mà mỗi lần sẽ đọc hết một lượng có kích thước ~{{a}^{b}}~ kilobyte, ở đây ~(a,b)~ là các số nguyên dương nào đó và ~b\ge 2;~ lúc này, nó sẽ tốn thời gian ~b~ giây cho dù giá trị của ~a~ là mấy.

Cụ thể hơn, với một tập tin kích thước ~n,~ đầu tiên, robot chọn một cặp ~({{a}_{1}},{{b}_{1}})~ như mô tả trên mà ~a_{1}^{{{b}_{1}}}\le n~ và tốn ~{{b}_{1}}~ giây để đọc; nếu như ~n-a_{1}^{{{b}_{1}}}>0~ thì vẫn còn thông tin chưa đọc xong, nó sẽ chọn tiếp một cặp ~({{a}_{2}},{{b}_{2}})~ nữa rồi tốn ~{{b}_{2}}~ giây để đọc phần tri thức còn lại và cứ thế, giả sử tổng cộng cần ~k~ lần. Như vậy, có ~k~ cặp số nguyên dương ~({{a}_{i}},{{b}_{i}}),\text{ }1\le i\le k~ và các số ~{{b}_{i}}\ge 2~ sao cho

~n=a_{1}^{{{b}_{1}}}+a_{2}^{{{b}_{2}}}+\cdots +a_{k}^{{{b}_{k}}}.~

Tổng thời gian robot cần sử dụng cho tập tin kích thước ~n~ này sẽ là ~{{b}_{1}}+{{b}_{2}}+\cdots +{{b}_{k}}.~
Anh quản lý thư viện, cũng là người yêu Toán và thích lập trình, đã tạo điều kiện thuận lợi cho Informath có thể kết nối đến máy chủ để đọc được các dữ liệu. Tuy vậy, cách đọc của robot làm anh liên tưởng đến một tính chất về biểu diễn số học khá thú vị như sau: "mỗi số tự nhiên luôn có thể viết thành tổng của không quá ~4~ số chính phương (chú ý, số chính phương là bình phương của một số tự nhiên); ngoài ra, các số có dạng đặc biệt là ~{{4}^{k}}(8m+7)~ với ~k,m~ là các số tự nhiên, thì không thể viết thành tổng của ít hơn ~4~ số chính phương được".

Ví dụ ~30={{5}^{2}}+{{2}^{2}}+{{1}^{2}},\text{ 4}={{2}^{2}},\text{ }2024={{42}^{2}}+{{16}^{2}}+{{2}^{2}}~ (nói thêm là các số này vẫn có thể biểu diễn được bởi tổng của nhiều số chính phương hơn, nhưng theo tính chất trên, luôn có cách biểu diễn chúng bởi tổng của không quá ~4~ số chính phương); còn số ~60=4\cdot (8\cdot 1+7)~ có dạng ~{{4}^{k}}(8m+7)~ nên cần dùng đến ~4~ số chính phương trở lên mới biểu diễn được nó, chẳng hạn ~{{6}^{2}}+{{4}^{2}}+{{2}^{2}}+{{2}^{2}}~ (không có cách nào dùng ít hơn ~4~ số chính phương). Anh quản lý thư viện đã chia sẻ tính chất trên cho Informath biết và robot thấy rằng sự thật thú vị này đúng là có liên quan ít nhiều đến cách đọc dữ liệu của nó, dù robot có thể xử lý được cả các số mũ lớn hơn ~2~ chứ không nhất thiết chỉ là các số chính phương. Từ sự gợi ý tình cờ đó, robot đã suy luận thêm và tính toán ra được phương án đọc dữ liệu nhanh nhất có thể, hãy cùng robot giải quyết vấn đề này nhé.

Yêu cầu: Để đọc hết lượng tri thức trong từng tập tin, hỏi Informath cần tốn ít nhất mấy giây (coi như thời gian nghỉ giữa hai lần liên tiếp để chọn các cặp số là không đáng kể)?

Input dòng đầu chứa ~T~ là số tập tin với ~1\le T\le 5.~ Trên ~T~ dòng tiếp theo, mỗi dòng sẽ có một số nguyên dương duy nhất không vượt quá ~{{10}^{9}}.~

Output In ra ~T~ số nguyên trên các dòng khác nhau theo thứ tự cho biết thời gian ít nhất mà robot Informath cần sử dụng để đọc từng tập tin trong thư viện.

Sample input 1

1
100000000

Sample output 1

2

Sample input 2

3
27
128
33

Sample output 2

3
4
5

Giải thích

Ở test 1, ta thấy ~{{10}^{8}}={{({{10}^{4}})}^{2}}~ nên theo cách học đặc biệt của Informath, nó chỉ tốn 2 giây. Đây là thời gian ít nhất cần sử dụng.

Ở test 2:

• Có ~27={{3}^{3}}~ nên robot chỉ cần đọc 1 lần với thời gian là 3 giây, đây cũng là số nhỏ nhất.
• Có ~128={{8}^{2}}+{{8}^{2}}~ nên cần đọc 2 lần, mỗi lần 2 giây nên tổng thời gian là 4 giây. Chú ý là nếu như xét ~128={{2}^{7}}~ thì nó cần thời gian đọc đến 7 giây, là nhiều hơn. Ngoài ra, ta cũng có thể kiểm tra được rằng không thể đọc trong ít hơn 4 giây nên thời gian ít nhất cần tìm là 4.
• Có ~33={{5}^{2}}+{{2}^{3}}~ nên nó cần đọc 2 lần với tổng thời gian là ~2+3=5~, đây là số nhỏ nhất.

gọi ~N~ là tổng kích thước của ~T~ tập tin:

• Có 20% số test ứng với 20% số điểm của bài thỏa mãn ~T~ tập tin đều có kích thước không vượt quá ~{{2}^{8}}.~
• Có 40% số test ứng với 40% số điểm của bài thỏa mãn: ~{{2}^{8}}<N\le {{2}^{16}}.~</li>
• Có 40% số test ứng với 40% số điểm của bài thỏa mãn: ~{{2}^{16}}<N\le {{10}^{9}}.~</li>

Huy đang học số học và rất yêu thích số ~x~. Nhưng vì chỉ yêu thích một số, nên khi được hỏi đưa ra nhiều số, Huy đã nghĩ ra định nghĩa "số gần yêu thích". Số gần yêu thích là số khác số yêu thích và kết thúc bằng số yêu thích của Huy.

Ví dụ khi ~x=24~ thì các số gần yêu thích là ~124,3524,22224,…~; các số ~204,2432,2240,…~ không phải số gần yêu thích.

Yêu cầu: Cho 2 số nguyên ~x,m~, hãy đếm số lượng số gần yêu thích không vượt quá ~m~.

Input

Một dòng duy nhất gồm 2 số nguyên ~x,m~ với ~1≤x≤10^5~ và ~1≤m≤10^{18}~.

Output

Một số nguyên dương là số lượng số gần yêu thích tìm được.

Input 1

3 17

Output 1

1

Input 2

24 1000

Output 2

9

Subtask

• 35% số test ~x<10;m≤1000;~
• 30% số test có ~m≤100000;~
• 35% số test còn lại không có ràng buộc bổ sung.

Cho số nguyên dương ~n~ và có hai bạn ~A, B~ sẽ chơi một trong hai trò chơi sau đây (~A~ luôn đi trước).

• Luật 1: ở mỗi lượt, người chơi sẽ trừ vào số hiện tại ước dương của nó mà ước đó khác ~1~ và khác chính số đó, cụ thể là nếu có ~x~ thì có thể chọn một trong các ước của nó là ~d~ mà ~1 < d < x~ và thay ~x \to x-d.~

• Luật 2: ban đầu, tất cả các ước của ~n~ sẽ được viết ra và ở lượt đầu tiên, ~A~ bắt buộc phải xóa số ~n.~ Ở mỗi lượt tiếp theo, người chơi sẽ xóa ước hoặc bội của số mà người kia xóa ở lượt đi trước đó.

Trong mỗi luật chơi, ai đến lượt đi của mình mà không thực hiện được thì thua cuộc. Vấn đề đặt ra là xác định người có chiến lược thắng, trong đó giả sử hai người đều có cách chơi tối ưu.

Hint: để giảm độ khó hơn, tác giả trò chơi có hint một tí như sau: ở luật 1, thử xét số ~n~ lẻ và sau đó xét luỹ thừa của ~2~ trong phân tích của số ~n~ (còn luật 2 thì dễ, SV tự giải).

Input

Dòng đầu tiên gồm số ~T~ cho biết số test, trong đó ~1 \le T \le 10.~ Mỗi dòng tiếp theo là giá trị của ~n~ trong test, trong đó ~1 \le n \le 10^9.~

Output

Với mỗi test, cho biết ai là người có chiến lược thắng. In ra ~A, A~ hoặc ~A, B~ hoặc ~B, A~ hoặc ~B, B~ một cách thích hợp.

Sample input

2
1
6

Sample output

B A
A B

Giải thích

Trong Ví dụ 1, với ~n=1~ thì theo luật ~1~ thì ~A~ không đi được lần nào; còn theo luật ~2~, người ~A~ sẽ xóa số ~1~ và ~B~ sẽ không còn gì để chơi. Trong Ví dụ 2, với ~n=6~ thì ở luật ~1~, người ~A~ có thể trừ ~n~ cho ~3~, khi đó còn lại ~3~ và ~B~ gặp số ~3~ thì thua ngay; còn ở luật ~2~, có các ước ~1,2,3,6~ ban đầu ~A~ đã xóa số ~6~ thì ~B~ xóa ~3~, đến lượt ~A~ chỉ có thể xóa ~1~ và tiếp theo ~B~ xóa ~2~ thì thắng luôn.

Xét hàm số ~f: \mathbb{Z}^+ \to \mathbb{Z}^+~ xác định bởi ~f(0) = 1~ và

~f(2n) = f(n-1)+f(n), \, f(2n+1) = f(n), \, n \le 1.~

Cho biết rằng mỗi số hữu tỷ ~p/q~ với ~p,q~ nguyên dương thì luôn có duy nhất một cách biểu diễn dưới dạng ~\frac{f(n)}{f(n+1)}.~ Xem hình minh họa bên dưới:

Yêu cầu đặt ra là cho trước các số ~p,q~, hãy tìm số ~n~ thỏa mãn biểu diễn trên.

Input

Hai số nguyên dương ~p,q~ với ~1 \le p,q \le 10^5.~

Output

Một số nguyên duy nhất là đáp số của bài toán. Kết quả có thể rất lớn nên lấy modulo ~10^9+7.~

Sample input 1

2 3

Sample output 1

5

Sample input 2

1 4

Sample output 2

7

Các Ví dụ 1, 2 có thể dễ dàng kiểm tra được trên sơ đồ đã cho.

Có ~50\%~ test của đề ứng với các số ~p,q \le 100~.

Trên một con đường, được coi như là một trục số dương xét từ 0 đến ~2^{31}-1,~ có hai công ty ~A~ và ~B~ nhận thi công lắp đặt đèn đường, trong đó ~A~ nhận thi công các đèn phía bên trái con đường còn ~B~ thì lo phía bên phải. Công ty A sẽ lắp đặt đèn đầu tiên ở vị trí a và cách ~d_1~ đơn vị độ dài thì đặt tiếp một cái nữa, và cứ thế lắp tại các vị trí có toạ độ ~a,a+d_1,a+2d_1,…~ Công ty ~B~ tương tự nhưng sẽ lắp đặt đèn đầu tiên ở vị trí ~b~ và cách ~d_2~ đơn vị độ dài thì đặt tiếp một cái nữa, và cứ thế lắp tại các vị trí có toạ độ ~b,b+d_2,b+2d_2,…~ (trong đó ~a,b,d_1,d_2~ đều là các số nguyên dương). Để rèn luyện sức khoẻ, bạn Lan muốn chạy bộ trên con đường này, xuất phát tại một vị trí L nguyên tuỳ ý nào đó thuộc ~[0;10^5]~ và chạy đến vị trí ~L+k~ với ~k~ nguyên. Do chạy vào lúc bình minh, lúc đèn đường không quá sáng nên bạn Lan chỉ thấy rõ cảnh vật hai bên đường ở vị trí x mà tại đó đều có đèn phía bên trái và bên phải. Bạn ấy muốn chọn vị trí xuất phát thích hợp để chạy qua được nhiều nhất những nơi có thể ngắm được cảnh hai bên đường, hãy giúp Lan nhé.

Xác định số lượng nhiều nhất các vị trí mà Lan có thể ngắm cảnh hai bên đường.

Input

Một dòng duy nhất gồm các số nguyên dương ~d_1,a,d_2,b,k~ (theo thứ tự đó) có giá trị không vượt quá ~10^9.~

Output

Một số nguyên duy nhất là số lượng lớn nhất các vị trí mà Lan có thể ngắm cảnh.

Sample input 1

2 1 2 2 2024

Sample output 1

0

Sample input 2

2 1000 4 1000 2024

Sample output 2

507

Sample input 3

2 1 3 1 1000000000

Sample output 3

166666667

Giải thích

Ở test 1, Cty A chỉ lắp đèn tại vị trí lẻ, còn cty B lắp ở vị trí chẵn nên không có vị trí nào mà có đèn của A lẫn B (với mọi cách chọn ~L~).

Ở test 2, Cty A lắp đèn ở vị trí chẵn ~≥1000~ còn cty B lắp đèn ở vị trí chia hết cho ~4~ kể từ ~100~ nên Lan có thể xuất phát từ vị trí ~1000~ là đi qua được ~507~ vị trí chia hết cho ~4~ từ ~1000 \to 3024~.

Ở test 3, Lan có thể xuất phát từ 1 và sẽ đi qua các vị trí chia 6 dư 1, ở đó cả hai bên đều có bóng đèn sáng. Từ 1 đến ~10^9~ sẽ có tất cả ~166666667~ vị trí như thế.

Subtask

• Có 30% số test ứng với 30% số điểm của bài thỏa mãn: ~k≤100.~
• Có 30% số test ứng với 30% số điểm của bài thỏa mãn: ~1≤d_1,d_2≤100.~
• CCó 40% số test ứng với 40% số điểm ứng với giới hạn ban đầu.