Một số nguyên \(X\) được gọi là số "gần hoàn hảo" nếu thoả mãn điều kiện: \(2 * X ≤ T\); với \(T\) là tổng các ước số dương của \(X\).

Ví dụ: số \(12\) là số "gần hoàn hảo" vì điều kiện \(2 * 12 ≤ 1 + 2 + 3 + 4 + 6 + 12\) đúng

Yêu cầu: Cho dãy số \(A\) có \(N\) phần tử nguyên dương \(a_1, a_2, a_3,..., a_N\), hãy kiểm tra xem các phần tử của dãy số \(A\) có phải là các số "gần hoàn hảo" hay không?

Input

• Dòng 1: chứa số nguyên dương \(N (N ≤ 10^6)\)
• Dòng 2: ghi N số nguyên dương \(a1, a2, a3,...,aN\) \((a_i ≤ 10^6\) với \(1 ≤ i ≤ N)\). Các số trên cùng một hàng ghi cách nhau bằng 1 dấu cách.

Output

• In ra màn hình \(N\) dòng, dòng thứ \(i\) ghi số \(1\) nếu số \(a_i\) là số gần hoàn hảo, ngược lại in ra số \(0\).

Example

3
6 16 12

1
0
1

Giới hạn

• Có \(15/25\) test tương ứng với \(30\%\) điểm với \(N ≤ 10^3\)
• Có \(10/25\) test tương ứng với \(20\%\) điểm với \(N ≤ 10^6\)