Một số nguyên X được gọi là "gần hoàn hảo" nếu thỏa mãn điều kiện:

2 × X ≤ T, trong đó T là tổng tất cả các ước số dương của X (bao gồm cả 1 và X).

Ví dụ: số 12 là gần hoàn hảo vì:

2 × 12 = 24 ≤ 1 + 2 + 3 + 4 + 6 + 12 = 28

Yêu cầu:

Cho dãy số A gồm N phần tử nguyên dương A₁, A₂, ..., A_N, hãy kiểm tra xem mỗi A_i có phải là số gần hoàn hảo không?

Dữ liệu vào (GHH.INP):

Dòng 1: Số nguyên dương N (N ≤ 10⁶).

Dòng 2: N số nguyên dương A₁, A₂, ..., A_N (1 ≤ A_i ≤ 10⁶), cách nhau bởi 1 dấu cách.

Dữ liệu ra (GHH.OUT):

Gồm N dòng, dòng thứ i ghi 1 nếu A_i là số gần hoàn hảo, ngược lại ghi 0.

Ví dụ:

GHH.INP

3
6 16 12

GHH.OUT

1
0
1

Giới hạn:

Có 15/25 test (tương ứng 3 điểm) với N ≤ 10³.

Có 10/25 test (tương ứng 2 điểm) với N ≤ 10⁶.