A Simple Problem#2761
Sign in

A Simple Problem

1 second
64 megabytes
Medium

For a given positive integer , find the smallest positive integer such that there exists an integer with

y^2 = n + x^2.

Input

The first line contains an integer , the number of test cases. Each of the following lines contains an integer (1 \leq n \leq 10^9).

Output

For each integer , output the value of on a separate line. If no such exists, output .

Examples

Example 1

Loading
Loading