Powers of 2

Determine whether each number in the array equals 2 raised to some non-negative integer power, returning 1 or 0.

输入格式

The first line contains n, and the second line contains n integers. Full original bounds: 1≤n≤100, 0≤a[i]≤50000000.

输出格式

Output n values 0 or 1 in input order, separated by spaces.

样例 1

输入：

5
1 2 3 4 0

输出：

1 1 0 1 0

样例 2

输入：

1
0

输出：

0

样例 3

输入：

2
33554432 50000000

输出：

1 0

样例说明

The outputs of the three public examples are, in order: 1 1 0 1 0; 0; 1 0. They were verified by independent enumeration or direct simulation.