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

Ví dụ: số 12 là một số "gần hoàn hảo" vì điều kiện $2*12 \le 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_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?

Dữ liệu vào:

• Dòng 1: Chứa số nguyên dương $N (N \le 10^6)$.
• Dòng 2: ghi $N$ số nguyên dương $A_1, A_2,..,A_N$ $(A_i \le 10^6$ với $1 \le i \le N)$. Các số trên cùng một hàng ghi cách nhau bằng 1 dấu cách.

Dữ liệu ra:

• Ghi ra $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 ghi số 0.

Ví dụ:

Giới hạn:

• Có 15/25 test tương ứng với 3 điểm với $N \le 10^3$
• Có 10/25 test tương ứng với 2 điểm với $N \le 10^6$