Problem Description

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

5
1112
4290
8716
9957
9095

23
65
67
244
70