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