Right-Coupled Numbers

An integer x is said to be a right-coupled number, if you can find two integers, say 0 < a ≤ b ≤ x such that a × b = x and a/b ≥ 0.5. In this problem, your task is to determine whether a given integer is a right-coupled number or not.

The first line of the input is an integer N denoting the number of test cases. Each test case is in one line, which contains a single integer 0 < x < 215.

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

• 1 ≤ N ≤ 1000
• 0 < x < 215