B. Kaosar Loves Divisors
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer $$$n$$$.

Note $$$f(n)$$$ as the number of even square divisors of $$$n$$$, and $$$g(n)$$$ as the number of odd square divisors of $$$n$$$.

An even square divisor of a positive integer $$$n$$$ is a divisor of $$$n$$$ that is both a perfect square and an even number. Similarly, an odd square divisor of $$$n$$$ is a divisor of $$$n$$$ that is both a perfect square and an odd number.

Your task is to calculate the value of $$$\frac{f(n)}{g(n)}$$$. It can be proven that the value is always an integer.

Input

The first line of the input will contain a single integer $$$t$$$ $$$(1 \le t \le 2 \cdot 10^5)$$$  — the total number of test cases.

Each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^{18}) $$$.

Output

For each test case, output in a new line — the value of $$$\frac{f(n)}{g(n)}$$$.

Example
Input
4
4
1
96
1000000000000000000
Output
1
0
2
9
Note

In the first test case, $$$f(4)=1$$$ because $$$4$$$ is the only even square divisor of $$$n$$$. And $$$g(4)=1$$$ because $$$1$$$ is the only odd square divisor of $$$n$$$. Thus, $$$\frac{f(n)}{g(n)}=\frac{1}{1}=1$$$.