A. Right-Coupled Numbers
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

An integer $$$x$$$ is said to be a right-coupled number, if you can find two integers, say $$$0 \le a \leq b \leq x$$$ such that $$$a \times b = x$$$ and $$$\frac{a}{b} \geq 0.5$$$. In this problem, your task is to determine whether a given integer is a right-coupled number or not.

Input

The first line of the input is an integer $$$N$$$ denoting the number of test cases ($$$1 \le N \le 1000$$$). Each test case is in one line, which contains a single integer $$$0 \lt x \lt 2^{15}$$$.

Output

If the given integer $$$x$$$ is a right-coupled number, output $$$1$$$; otherwise, output $$$0$$$. Each is in a single line.

Example
Input
4
66
55
105
150
Output
1
0
0
1