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.
First line of input consists of T the number of test cases. Each test consists of N.
Print in each line the minimum number of cupcakes Pritam throws or buys.
1 <= T <= 10000
1 <= N <= 1012
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.