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\cdot X\le 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\cdot 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,\ldots,A_N\), hãy kiểm tra xem các phần tử của dãy số \(A\) có phải “gần hoàn hảo” hay không?

Input

• Dòng đầu chứa một số nguyên dương \(N\).
• Dòng 2 ghi \(N\) số nguyên dương \(A_i\) cách nhau bởi một dấu cách.

Output

• In ra \(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=\overline{1,N}\)

Constraints

• \(1\le N<10^6\)
• \(1\le A_i\le 10^6\)

Subtasks

• Có \(15/25\) test với \(N\le 10^3\)
• Có \(10/25\) test với \(10^3<N<10^6\)

Example