Đề bài

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

Ví dụ số 12 là một số "gần hoàn hảo" vì điều kiện: \(2 \times 12 \leq 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: Ghi số nguyên dương N (\(N \leq 10^6\));

Dòng 2: Ghi N số nguyên dương \(A_1, A_2,...,A_N (A_i \leq 10^6)\) với \(1 \leq i \leq N\). Các số trên cùng một dòng, cách nhau bởi dấu cách.

Dữ liệu ra:

Gồm N 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, với \(i=1,2,...,N\)

Ví dụ:

Input:

3 
6  16  12

Output:

1 
0 
1