In the 2-D world of Flatland, the Circles were having their sports day and wanted to end it with a nice formation. So, they called upon Mr. Sphere from Spaceland for help. Mr Sphere decides to arrange the Circles in square formations. He starts with $N$ Circles and forms the largest possible square using these Circles. He then takes the remaining Circles and repeats the procedure. A square of side $S$ requires $S^2$ Circles to create.
Find the number of squares he will be able to form at the end of the process.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow.
- Each testcase contains of a single integer $N$.

-----Output:-----
For each testcase, output a single integer denoting the number of squares.

-----Constraints-----
- $1 \leq T \leq 1000$
- $1 \leq N \leq 1000$

-----Sample Input:-----
2

85

114          

-----Sample Output:-----
2

4

-----EXPLANATION:-----
Test case 1 : Mr Sphere forms a square of side 9 using 81 Circles and then forms a square of side 2 using the remaining 4.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
import math
for _ in range(int(input())):
 n=int(input())
 c=0
 while(n>0):
  i=int(math.sqrt(n))
  c+=1
  n=n-i**2
 print(c)
  


l = []
for _ in range(int(input())):
  n = int(input())
  count = 0
  while n>0:
   r = int(n ** 0.5)
   n = n - r*r
   count+=1
  l.append(count)
for i in l:
  print(i)

for _ in range(int(input())):
  n = int(input())
  count = 0
  while n>0:
   r = int(n ** 0.5)
   n = n - r*r
   count+=1
  print(count)

import math
n=int(input())
l=[]
for i in range(0,n):
 n1=int(input())
 count=0
 while n1>0:
  s=int(math.sqrt(n1))
  n1=n1-(s*s)
  count+=1 
 l.append(count)
for i in l:
 print(i)



for t in range(int(input())):
 n = int(input())
 sqrs = 0
 sizeSqr = 0
 while True:
  if n < 1:
   break
  i = 1
  while True:
   if i * i > n:
    sqrs += 1
    sizeSqr = i - 1
    break
   elif i * i == n:
    sqrs += 1
    sizeSqr = i
    break
   i += 1
  n = n - sizeSqr**2
 print(sqrs)

import math
try:
 t = int(input())
 for i in range(t):
  c=-0
  x = int(input())
  while x!=0:
   x-=math.floor(math.sqrt(x))**2
   c+=1
  print(c)
except:
 pass

import math
for _ in range(int(input())):
 count = 0
 n = int(input())
 while(n != 0):
  x = int(math.sqrt(n))
  count += 1
  n = n - x*x
 print(count)

# cook your dish here
T=int(input())
for i in range(0,T):
 N=int(input())
 count=0
 while N!=0:
  N=N-(((N**0.5)//1)**2)
  count+=1
 print(count)

# cook your dish here
import math
for _ in range(int(input())):
 n=int(input())
 s=0
 while n!=0:
  s+=1
  n-=(int(math.sqrt(n)))**2
 print(s)

# cook your dish here
import math
for _ in range(int(input())):
 n=int(input())
 s=0
 while n!=0:
  s+=1
  n-=(int(math.sqrt(n)))**2
 print(s)

t=int(input())
i=0
while i<t:
 n=int(input())
 j=n
 b=0
 while n>0 :
  r=int(n**(0.5))
  b+=1
  n=n-r**2
 print(b)
 i+=1

t=int(input())
i=0
while i<t:
 n=int(input())
 j=n
 c=0
 while n>0:
  r=int(n**(0.5))
  c+=1
  n=n-r**2
 print(c)
 i+=1

t=int(input())
i=0
while i<t:
 n=int(input())
 j=n
 c=0
 while n>0:
  r=int(n**(0.5))
  c+=1
  n=n-r**2
 print(c)
 i+=1

# cook your dish here
x = int(input())
for i in range(x):
 a = int(input())
 j = 0
 while a!=0:
  b = int(a**0.5)
  a -= b**2
  j += 1
 print(j)

import math
for t in range(int(input())):
 n=int(input())
 c=0
 while n>0:
  r=int(math.sqrt(n))
  n=n-(r*r)
  c+=1 
 print(c)
 


import math
t=int(input())
for _ in range (t):
 n=int(input())
 c=0
 while n>0:
  r=int(math.sqrt(n))
  n=n-(r*r)
  c=c+1
 print(c)


# cook your dish here
import math
for _ in range(int(input())):
 n=int(input())
 c=0
 while n>0:
  r=int(math.sqrt(n))
  n=n-(r*r)
  c=c+1
 print(c)

# cook your dish here
import math
def Solution():
 t=int(input())
 for i in range(t):
  n=int(input())
  c=0
  while(n):
    t=int(math.sqrt(n))
    c+=1
    n=n-(t**2)
  print(c)

Solution()

# cook your dish here
import math
t=int(input())
for i in range(t):
 n=int(input())
 c=0
 while(n):
  t=int(math.sqrt(n))
  c+=1
  n=n-(t**2)
 print(c)

import math
for _ in range(int(input())):
 N=int(input())
 count=0
 while N>0:
  n=int(math.sqrt(N))
  N=N-(n**2)
  count=count+1
  
 print(count)
  


# cook your dish here
import math
t=int(input())
for _ in range(t):
 a=int(input())
 x1=math.floor(math.sqrt(a))
 x2=a-(x1*x1)
 c=0
 while(1):
  c=c+1
  if x2==0:
   print(c)
   break
  x1=math.floor(math.sqrt(x2))
  x2=x2-(x1*x1)


for i in range(int(input())):
 n = int(input())
 count = 0
 while n > 0:
  k = 1
  while k*k <= n:
   k += 1
  n -= (k-1)*(k-1)
  count += 1
 print(count)

for i in range(int(input())):
 import math
 n=int(input())
 f=c=0
 while(n>=1):
  f=math.floor(math.sqrt(n))
  c+=1
  n=n-f*f
 print(c)

import math
t = int(input())
while(t!=0):
 n = int(input())
 c = 0
 while(n!=0):
  n = n - (int(math.sqrt(n))**2)
  c +=1
 t = t-1
 print(c)