Given a number x, ask positive integer $y\geq 2$, that satisfy the following conditions:
1. The absolute value of y - x is minimal
2. To prime factors decomposition of Y, every element factor appears two times exactly.
Input
The first line of input is an integer T ( $1\leq T \leq50 $)
For each test case£¬the single line contains, an integer x ( $1\leq x \leq {10} ^ {18} $)
Output
For each testcase print the absolute value of y - x
