Examples of good practices

A square number is an integer number that can be represented in a form of a square of the other integer number. For example, number 25 is a square number because 25 = 5². In a contrary, number 18 is not a square number because there is no integer number k for which k² = 18.

You are asked to find the closest square number for a given integer number. The distance between two numbers n and m is defined by the absolute value of their difference, i.e. dist(n,m) = |n - m|.

Input

The first line of the input consist of a single integer number t which determines the number of tests.

In each of next t lines there is a single integer number n.

Constraints

• 0 < t ≤ 1000
• 0 < n ≤ 50 000 000

Output

For each number n print its closest square number. Separate your answers with a new line character.

Example

Input:
4
11
23
99
101

Output:
9
25
100
100