Chef played an interesting game yesterday. This game is played with two variables $X$ and $Y$; initially, $X = Y = 0$. Chef may make an arbitrary number of moves (including zero). In each move, he must perform the following process:
- Choose any positive integer $P$ such that $P \cdot P > Y$.
- Change $X$ to $P$.
- Add $P \cdot P$ to $Y$.
Unfortunately, Chef has a bad memory and he has forgotten the moves he made. He only remembers the value of $X$ after the game finished; let's denote it by $X_f$. Can you tell him the maximum possible number of moves he could have made in the game?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single integer $X_f$.

-----Output-----
For each test case, print a single line containing one integer — the maximum number of moves Chef could have made.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le X_f \le 10^9$

-----Example Input-----
3
3
8
9

-----Example Output-----
3
5
6

-----Explanation-----
Example case 2: One possible sequence of values of $X$ is $0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 5 \rightarrow 8$.

Difficulty: interview

Starter code:

Solutions:
from math import sqrt

T = int(input())
ans = []

for _ in range(T):
 X = int(input())

 count = 0
 x = 0
 y = 0
 while(x<=X):
  p = int(sqrt(y))
  count += 1
  if(p*p>y):
   x = p
   y += p**2
  else:
   x = p+1
   y += (p+1)**2
 if(x<=X):
  ans.append(count)
 else:
  ans.append(count-1)

for i in ans:
 print(i)

# cook your dish here
import math
t = int(input())
for _ in range(t):
 xf = int(input())
 ans = 0
 x,y = 0,0
 while x<=xf:
  p = int(math.sqrt(y))
  if p*p>y:
   x = p
   y = y + p*p
   ans = ans + 1
  else:
   x = p+1
   y = y + (p+1)*(p+1)
   ans = ans + 1
 if x<=xf:
  print(ans)
 else:
  print(ans-1)

# cook your dish here
import math
T=int(input())
for i in range(T):
 x=int(input())
 temp,count,y=0,0,0
 p=0
 while(temp<=x):
  p=int(math.sqrt(y))
  if(p*p>y):
   temp=p
   y+=p*p
   count+=1
  else:
   p+=1
   temp=p
   y+=p*p
   count+=1
 if(temp>x):
  print(count-1)
 elif(temp<=x):
  print(count)

# cook your dish here
import math
T=int(input())
for i in range(T):
 x=int(input())
 temp,count,y=0,0,0
 p=0
 while(temp<=x):
  p=int(math.sqrt(y))
  if(p*p>y):
   temp=p
   y+=p*p
   count+=1
  else:
   p+=1
   temp=p
   y+=p*p
   count+=1
 if(temp>x):
  print(count-1)
 elif(temp<=x):
  print(count)

# cook your dish here
import math
test=int(input())
for _ in range(test):
 last=int(input())
 x=0
 y=0
 c=0
 while True:
  if y>=last*last:
   print(c)
   break
  c+=1
  x=int(math.sqrt(y))+1
  y=y+x*x





# cook your dish here
import math
test=int(input())
for _ in range(test):
 last=int(input())
 x=0
 y=0
 c=0
 while True:
  if y>=last*last:
   print(c)
   break
  c+=1
  x=int(math.sqrt(y))+1
  y=y+x*x





# cook your dish here
import math
for _ in range(int(input())):
 last=int(input())
 x=0
 y=0
 c=0
 while True:
  if y>=last*last:
   print(c)
   break
  c+=1
  x=int(math.sqrt(y))+1
  y=y+x*x





# cook your dish here
from math import ceil

for i in range(int(input())):
 xf=int(input())
 x=0
 y=0
 p=1
 step=0
 while(x<=xf):
  x=p
  y+=(p*p)
  p=ceil(y**0.5)
  step+=1
 print(step-2) 

# cook your dish here
from math import ceil

for i in range(int(input())):
 xf=int(input())
 x=0
 y=0
 p=1
 step=0
 while(x<=xf):
  x=p
  y+=(p*p)
  p=ceil(y**0.5)
  step+=1
 print(step-2) 

from math import sqrt, ceil
import time
from bisect import bisect_right
start_time = time.time()

a = []
x = 0
y = 0
while x <= 10 ** 9:
 x = int(sqrt(y))+1
 a.append(x)
 y += x * x

end_time = time.time()
# print(end_time - start_time)

# print(len(a))
# print(a)
# print(b)
for _ in range(int(input())):
 n = int(input())
 print(bisect_right(a,n))
 
 
 


from math import ceil

for i in range(int(input())):
 xf=int(input())
 x=0
 y=0
 p=1
 step=0
 while(x<=xf):
  x=p
  y+=(p*p)
  p=ceil(y**0.5)
  step+=1
 print(step-2) 

# cook your dish here
import math
t = int(input())
for i in range(t):
 n = int(input())
 num,x,y,count = 1,0,0,0
 while(num * num > y and num <= n):
  y = y + num*num
  x = num
  count += 1
  num = math.floor(math.sqrt(y))+1
  
 print(count)

import sys
import math
input=sys.stdin.readline
for _ in range(int(input())):
 n=int(input())
 x=0
 y=0
 ans=0
 while x<=n:
  z=int(math.sqrt(y))
  z+=1
  y+=(z*z)
  x=z
  ans+=1
 print(ans-1)

import math
t = int(input())
for T in range(t):
 xf = int(input())
 x, y = 0, 0
 p = 1
 val = 0
 while(x <= xf):
  x = p
  y += (p * p)
  p = math.ceil(math.sqrt(y))
  val += 1
 print(val - 2)


import math
t = int(input())
for T in range(t):
 xf = int(input())
 x, y = 0, 0
 p = 1
 val = 0
 while(x <= xf):
  x = p
  y += (p * p)
  p = math.ceil(math.sqrt(y))
  val += 1
 print(val - 2)

import sys
from math import sqrt
try:    
 sys.stdin=open('inp.txt','r')
except: pass
def helper():
 pass
t=int(input())
for _ in range(t):
 n=int(input())
 x=0
 y=0
 k=0
 while x<=n:
  a=int(sqrt(y))
  a+=1
  x=a
  y+=(a*a)
  k+=1
 print(k-1)

# cook your dish here
import math
t = int(input())
while(t):
 n = int(input())
 res = 0
 x = 0
 y = 0
 while(x <= n):
  tmp = int(math.sqrt(y))
  tmp += 1
  y += tmp * tmp
  x = tmp
  res += 1
 
 print(res - 1)
 
 t -= 1

# cook your dish here
import math
l=[0,1,2,3,4,6,9,13]
s=316
while l[-1]<10**9:
 l.append(math.floor(math.sqrt(s))+1)
 s+=l[-1]**2
#print(l)
n=int(input())
while n>0:
 n-=1
 a=int(input())
 c=0
 for i in l:
  if i<=a:
   c+=1
  else:
   break
 print(c-1)
 
 


for _ in range(int(input())):
 num = int(input())
 
 moves = 0
 x,y = 0,0
 
 while x<=num:
  x = int(y**0.5)+1
  y += x*x
  moves += 1

 print(moves-1)


import math
for _ in range(int(input())):
 tt=int(input())
 x=y=moves=0
 while x<tt and y<(tt**2):
  x=math.floor(math.sqrt(y))+1
  y=y+x**2
  moves+=1 
 print(moves)

import math
def binarySearch (arr, l, r, x):
 mid = (l+r)//2
 if arr[mid] == x: 
  return mid
 elif arr[mid] > x: 
  return binarySearch(arr, l, mid-1, x) 
 elif (arr[mid]<x and arr[mid+1]>x):
  return mid
 else: 
  return binarySearch(arr, mid + 1, r, x)

def vceil(k):
 if(math.ceil(k)==k):
  return int(k+1)
 else:
  return math.ceil(k)
dp=[1]
i=1
sum=0
while(i<=10**9):
 sum+=i**2
 i=math.sqrt(sum)
 i=vceil(i)
 dp.append(i)

t=int(input())
for _ in range(t):
 n=int(input())
 ans=binarySearch(dp, 0, len(dp), n)
 ans=ans+1
 print(ans)


from math import sqrt
for _ in range(int(input())):
 n=int(input())
 j=0
 x,y=0,0
 k=0
 while(x!=n):
  j+=1
  if(j<=n):
   x=j
  if(y>=j*j):
   j=int(sqrt(y))
   continue
  if(y+j*j<n*n and x!=n):
   y+=j*j
  else:
   x=n
  k+=1
 print(k)