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~