Go Back

##### Pritam Likes Cupcakes (250)

Description

Pritam has decided to throw a party for passing his CCDSAP Exam.

He has decided to keep **N** cupcakes for the party. Unfortunately, Pritam needs the number of cupcakes to be square of any real number. He can throw away some cupcakes or buy new ones.

Tell us how many minimum cupcakes in total Pritam needs to throw or buy so that it becomes a square of any real number.

Input

First line of input consists of **T** the number of test cases. Each test consists of **N**.

Output

Print in each line the minimum number of cupcakes Pritam throws or buys.

Constraints

1 <= T <= 10000

1 <= N <= 10^{12}

Example

Copy Input

**Input:**

3

1

3

6**Output:**

0

1

2

Explanation

Case 1: Pritam has already square numbered cupcakes.

Case 2: Pritam can throw 2 cupcakes (N-2=1) or buy one more(N+1=4). Ans = min(2,1) = 1.

Case 3: Pritam can throw 2 or buy 3 cupcakes it doesn't matter so Ans = min(2,3) = 2.

There was a mistake encountered in setting of SRM02A and SRM02B. Points for Wrong Answer has been retracted. You can make submissions for SRM02A and SRM02B now. We apologise for the inconvenience.

For SRM02A: Output should have an exact precision of 2 digits after decimal.

Constraints are 1 <= T <= 100000