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: EASY
Tags: Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	squers = 0
	while n >= 1:
		c = int(n ** 0.5)
		squers += 1
		n = n - c ** 2
	print(squers)


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


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


def test(num, o, count):
	if num <= 0:
		return count
	if o ** 2 > num:
		count += 1
		return test(num - (o - 1) ** 2, 1, count)
	else:
		return test(num, o + 1, count)
for _ in range(int(input())):
	num = int(input())
	print(test(num, 1, 0))


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


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)


import math
for i in range(int(input())):
	N = int(input())
	x = int(math.sqrt(N))
	c = 1
	y = N - x ** 2
	while y > 0:
		c += 1
		z = int(math.sqrt(y))
		y = y - z ** 2
	print(c)


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
for _ in range(int(input())):
	n = int(input())
	c = 0
	while n > 0:
		n = n - int(math.sqrt(n)) ** 2
		c += 1
	print(c)


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


T = int(input())
for x in range(T):
	n = int(input())
	c = 0
	while n > 0:
		k = int(n ** 0.5)
		n -= k * k
		c += 1
	print(c)


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


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

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()


for i in range(int(input())):
	n = int(input())
	c = 0
	while n > 0:
		i = 1
		while i * i <= n:
			i = i + 1
		n = n - (i - 1) * (i - 1)
		c = c + 1
	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)


t = int(input())
for tc in range(t):
	n = int(input())
	c = 0
	while n > 0:
		m = int(n ** 0.5)
		n = n - m * m
		c += 1
	print(c)


for i in range(int(input())):
	x = int(input())
	d = 0
	while x > 0:
		y = int(x ** (1 / 2))
		y = y * y
		x = x - y
		d += 1
	print(d)


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


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)


t = int(input())
for i in range(t):
	c = int(input())
	d = c
	n = 0
	while d != 0:
		if d * d <= c:
			n += 1
			c = c - d * d
			d = c
		else:
			d = d - 1
	print(n)


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


t = int(input())
for i in range(t):
	n = int(input())
	l = [0] * 36
	for i in range(1, 36):
		l[i] = i * i
	c = 0
	while n != 0:
		for i in range(1, 36):
			if l[i] <= n and l[i + 1] > n:
				c += 1
				n = n - l[i]
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	while n > 0:
		x = int(n ** 0.5)
		n = n - x * x
		c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	s = 0
	l = []
	i = 1
	while n > 0:
		if i * i < n:
			i += 1
			continue
		if i * i == n:
			l.append(i)
			n = n - i * i
		else:
			l.append(i - 1)
			n = n - (i - 1) * (i - 1)
		i = 1
	print(len(l))


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)


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

def bis(a, l, h, v):
	while l <= h:
		m = (l + h) // 2
		if a[m] == v:
			return v
		elif a[m] < v:
			l = m + 1
		else:
			h = m - 1
	if l == 0:
		while a[l] < v:
			l += 1
		return a[l - 1]
	else:
		while a[h] > v:
			h -= 1
		return a[h]
for i in range(int(input())):
	n = int(input())
	a = [j * j for j in range(0, 31)]
	ans = 0
	while n:
		b = math.floor(math.sqrt(n))
		ans += 1
		n -= b * b
	print(ans)


import math
for i in range(int(input())):
	n = int(input())
	a = [j * j for j in range(0, 31)]
	ans = 0
	while n:
		b = math.floor(math.sqrt(n))
		ans += 1
		n -= b * b
	print(ans)


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


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


import math
for i in range(int(input())):
	n = int(input())
	count = 0
	while True:
		r = int(math.sqrt(n))
		count += 1
		n = n - r ** 2
		if n < 1:
			break
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	new = n
	while n != 0:
		h = int(n ** (1 / 2))
		new = new - h ** 2
		c = c + 1
		n = new
	print(c)


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)


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)


from math import *
for i in range(int(input())):
	c = 0
	n = int(input())
	while n > 0:
		x = int(n ** 0.5)
		n = n - x * x
		c += 1
	print(c)


for _ in range(int(input())):
	N = int(input())
	circles = N
	count = 0
	while circles != 0:
		i = 1
		while i * i <= circles:
			i += 1
		side = i - 1
		count += 1
		circles = circles - side * side
	print(count)


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


import math
t = int(input())
for i in range(t):
	n = int(input())
	sq = 0
	while n != 0:
		sq += 1
		n = n - int(math.sqrt(n)) ** 2
	print(sq)


t = int(input())
for i in range(t):
	n = int(input())
	count = 0
	while n >= 1:
		sq = int(n ** 0.5)
		count = count + 1
		n = n - sq ** 2
	print(count)


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


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


for i in range(int(input())):
	n = int(input())
	squares = 0
	while n >= 1:
		c = int(n ** 0.5)
		squares += 1
		n = n - c ** 2
	print(squares)


import math
testcases = int(input())
while testcases > 0:
	n = int(input())
	count = 0
	while n > 0:
		count += 1
		sqrt = math.floor(math.sqrt(n))
		n -= sqrt ** 2
	print(count)
	testcases -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	c = 0
	while n > 0:
		n1 = int(n ** 0.5)
		n = n - n1 ** 2
		c += 1
	print(c)


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)


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 _ in range(int(input())):
	n = int(input())
	sqrs = [0] * 36
	for i in range(1, 36):
		sqrs[i] = i * i
	count = 0
	while n > 0:
		for i in range(1, 36):
			if sqrs[i] <= n and sqrs[i + 1] > n:
				count += 1
				n = n - sqrs[i]
	print(count)


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


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


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)


t = int(input())
for j in range(t):
	n = int(input())
	l = []
	i = 1
	while n > 0:
		if i * i < n:
			i = i + 1
			continue
		if i * i == n:
			l.append(i)
			n = n - i * i
		else:
			l.append(i - 1)
			n = n - (i - 1) * (i - 1)
		i = 1
	print(len(l))


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


t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	while 1:
		s = n ** (1 / 2) // 1
		n = n - s ** 2
		c = c + 1
		if n == 0:
			print(int(c))
			break


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


for tc in range(int(input())):
	n = int(input())
	m = n
	s = 1
	count1 = 0
	while s > 0:
		c = int(m ** 0.5)
		s = m - c * c
		m = s
		count1 += 1
	print(count1)


t = int(input())
import math
for i in range(t):
	a = int(input())
	s = 0
	while a > 0:
		b = int(math.sqrt(a))
		a = a - b * b
		s = s + 1
	print(s)


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


import math
for i in range(int(input())):
	count = 0
	n = int(input())
	while n != 0:
		s = int(math.sqrt(n))
		di = n - s ** 2
		count += 1
		n = di
	print(count)