Nhập vào từ bàn phím hai số nguyên dương m, n (m, n <= 10¹⁶). Hãy viết chương trình in ra màn hình dạng tối giản của phân số m/n.

Ví dụ:

Một bộ ba số nguyên dương (x; y; z) được gọi là một bộ ba số nguyên Pythagore nếu bình phương của một số nào đó bằng tổng bình phương của 2 số còn lại. Chẳng hạn: Bộ ba số (3; 4; 5) có 5² = 3² + 4² là một bộ ba số Pythagore.

Yêu cầu: Nhập từ bàn phím 2 số nguyên dương x và y (x, y <=300000). Hãy tìm và in ra màn hình một số nguyên dương z sao cho bộ ba số nguyên (x; y; z) là một bộ ba số nguyên Pythagore.

Chú ý: Nếu không có số nguyên dương z nào thỏa mãn thì in ra màn hình số 0

Ví dụ:

Hôm nay là một ngày đẹp trời như bao ngày, anh Sơn quyết định tổ chức cuộc thi "Thắng làm vua, thua thì làm thêm bài tập". Cụ thể anh đưa ra một con số, hãy kiểm tra xem số đó có phải là hợp số hay không.
Input: Nhập từ màn hình một số nguyên dương n (n<10¹⁴).

Output: In ra "YES" nếu n là hợp số, ngược lại in ra "NO".

Một số được gọi là gần nguyên tố nếu nó có chính xác 2 ước nguyên tố. Ví dụ, 6, 18, 24 là số gần nguyên tố, trong khi 4, 8, 9, 42 thì không. Tìm tất cả các số gần nguyên tố từ 1 tới n.

INPUT: Một dòng chứa số nguyên n (1 <= n <= 3000)

OUTPUT: Số số gần nguyên tố từ 1 đến n.

Một số nguyên dương ~N~ được gọi là số gần hoàn hảo nếu thỏa mãn điều kiện: ~2 * N \le A~, với ~A~ là tổng các ước số của ~N~. Chẳng hạn: ~12~ là một số "gần hoàn hảo" vì: ~2 * 12 < 1 + 2 + 3 + 4 + 6 + 12~.

Yêu cầu:

Với ~K~ số nguyên dương, hãy kiểm tra xem các số nguyên dương đó có phải là số "gần hoàn hảo" hay không

Input

• Dòng đầu tiên chứa số nguyên dương ~K~ ~(1 \le K \le 100)~,
• Dòng thứ hai chứa ~K~ số nguyên không âm ~A_1, A_2, A_3, …, A_K~.~(0 \le A_i \le 10^9)~ với ~(1 \le i \le K)~.

Output

• Gồm ~K~ dòng, dòng thứ ~i~ ghi số ~1~ nếu ~A_i~ là số "gần hoàn hảo", ngược lại ghi số ~0~.

Scoring

• Subtask ~1~ (~60\%~ số điểm): ~A_i \le 10^6~ với ~1 \le i \le K~.
• Không có ràng buộc gì thêm

Ví dụ

Input

3
6 16 12

Output

1
0
1