Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

When the final results for the employement competition were announced, Nour Eddin Ramadan was thrilled to find his name among the accepted co-Chefs.

However, after a while Nour started wasting time at the kitchen. He would usually spend hours talking to girls, and he even invited a girl to the kitchen pretending that he is the most valuable employer at Chef's restaurant.

When Chef found out about it, he decided that it was time to teach Nour a lesson. Before going home that night, Chef called Nour to his office and asked him to solve the following problem, saying that he better come to work tomorrow with a solution for it, or otherwise, it would be better if he doesn't come at all:

Given T queries, where each query contains a single number Y, Nour has to find the number of pairs A and B, such that the following equation holds true:

A^{2} + B ≤ Y

Where A is any positive integer, and B holds (1 ≤ B ≤ 700).

Nour was really busy that night (Yeah he got that girl to go out with him after all!), and he asked for your help.
 
------ Input ------ 

The first line contains T denoting the number of test cases.

T lines follows, Each line contains a single integer Y denoting the right side of the formula.

------ Output ------ 

For each test print a single line, containing a single number, indicating the answer for the test.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ Y ≤ 10^{10}$
$Note that A must be any positive integer, and B must hold 1 ≤ B ≤ 700.$

----- Sample Input 1 ------ 
4

2

3

4

10000000000
----- Sample Output 1 ------ 
1

2

3

69999300

Difficulty: MEDIUM
Tags: Mathematics

Complete search
Skill types: Complete search

Starter code:

Solutions:
import math
t = int(input())
while t:
	t -= 1
	n = int(input())
	if n > 700:
		x = n - 700
		v = math.floor(math.sqrt(x))
		u = math.ceil(math.sqrt(n) - 1)
		ans = 700 * v
		y = (u - v) * n - u * (u + 1) * (2 * u + 1) // 6 + v * (v + 1) * (2 * v + 1) // 6
		ans += y
	else:
		u = math.ceil(math.sqrt(n) - 1)
		ans = u * n - u * (u + 1) * (2 * u + 1) // 6
	print(ans)


for t in range(int(input())):
	a = int(input())
	k = 0
	l = 0
	if a > 700:
		l = int((a - 700) ** 0.5)
		k += l * 700
	m = int(a ** 0.5)
	k += a * (m - l)
	k -= m * (m + 1) * (2 * m + 1) // 6
	k += l * (l + 1) * (2 * l + 1) // 6
	print(k)


import math

def solve(n):
	ans = 0
	bound = max(math.ceil(math.sqrt(n - min(700, n))), 1)
	for i in range(bound, math.ceil(math.sqrt(n))):
		ans += n - i * i
	return ans + 700 * (bound - 1)
for _ in range(int(input())):
	print(solve(int(input())))


for _ in range(int(input())):
	y = int(input())
	count = 0
	a = int(pow(y, 0.5))
	while a > 0 and a * a >= y - 700:
		count += y - a * a
		a -= 1
	print(a * 700 + count)


import math
t = int(input())
for case in range(t):
	y = int(input())
	if y == 1:
		print(0)
		continue

	def baseoflargestsquarelessthan(num):
		return int(math.floor(math.sqrt(num)))

	def sumofsquaresupto(k):
		return k * (k + 1) * (2 * k + 1) / 6
	b = baseoflargestsquarelessthan(y)
	if y <= 701:
		print(int(b * y - sumofsquaresupto(b)))
		continue
	z = baseoflargestsquarelessthan(y - 701)
	suma = z * 700
	print(int(suma + (b - z) * y - (sumofsquaresupto(b) - sumofsquaresupto(z))))


t = int(input())
for x in range(t):
	y = int(input())
	c = 0
	if y > 700:
		t = y - 700
		a = int(t ** 0.5)
		c += a * 700
		a += 1
		while a ** 2 < y:
			c += y - a ** 2
			a += 1
	else:
		a = 1
		while a ** 2 < y:
			c += y - a ** 2
			a += 1
	print(c)


T = int(input())

def solve():
	import math
	count = 0
	Y = int(input())
	if Y > 700:
		temp = Y - 700
		A = math.sqrt(temp) // 1
		count = int(A * 700)
		A = int(A) + 1
		while A ** 2 < Y:
			B = Y - A ** 2
			count += B
			A += 1
		print(int(count))
	else:
		A = 1
		while A ** 2 < Y:
			B = Y - A ** 2
			if B <= 700:
				count += B
			elif B > 700:
				count += 700
			A += 1
		print(count)
for _ in range(T):
	solve()


import math
for _ in range(int(input())):
	y = int(input())
	a = math.floor(y ** 0.5)
	b = math.floor(max(0, y - 700) ** 0.5)
	ans = b * 700
	for i in range(b + 1, a + 1):
		ans += y - i ** 2
	print(ans)


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


from bisect import bisect_left, bisect_right
from heapq import heapify, heappush, heappop
from cmath import pi
from distutils import extension
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
a = []
for i in range(10 ** 5 + 1):
	a.append(i * i)
for _ in range(ii()):
	y = ii()
	if y == 1:
		print(0)
		continue
	c = 0
	val = int(sqrt(y - 1))
	for i in range(val, 0, -1):
		if y - a[i] <= 700:
			c += y - a[i]
		else:
			c += 700 * i
			break
	print(c)


from math import *
t = int(input())

def func(y, t):
	return y * t - int(t * (t + 1) * (2 * t + 1) / 6)
for alpha in range(t):
	y = int(input())
	t = int(sqrt(y))
	ans = func(y, t)
	if y <= 701:
		print(ans)
		continue
	else:
		z = int(sqrt(y - 700))
		ans = ans + 700 * z
		ans = ans - func(y, z)
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	x = int(pow(max(n - 700, 0), 0.5))
	ans = x * 700
	x += 1
	d = x * x
	while d <= n:
		ans += min(700, n - d)
		x += 1
		d = x * x
	print(ans)


import math
T = int(input())
for _ in range(T):
	n = int(input())
	m = math.sqrt(n)
	k = int(m)
	ans = 0
	for i in range(k, 0, -1):
		a = n - i ** 2
		if a <= 700:
			ans += a
		else:
			ans += 700 * i
			break
	print(ans)


T = int(input())
for i in range(T):
	n = int(input())
	x = int(pow(max(n - 700, 0), 0.5))
	ans = x * 700
	x += 1
	d = x * x
	while d <= n:
		ans += min(700, n - d)
		x += 1
		d = x * x
	print(ans)


from math import *

def sos(x):
	return int(x * (x + 1) * (2 * x + 1) / 6)
t = int(input())
for _ in range(t):
	y = int(input())
	astart = 0
	if y <= 700:
		astart = 1
	else:
		astart = ceil((y - 700) ** 0.5)
	aend = int(y ** 0.5)
	mul = aend - astart + 1
	print(y * mul - sos(aend) + sos(astart - 1) + (astart - 1) * 700)


from math import sqrt

def find(X):
	return int(sqrt(X))
for _ in range(int(input())):
	Y = int(input())
	if Y <= 150000:
		result = 0
		for i in range(1, 701):
			p = Y - i
			if Y - i <= 0:
				break
			else:
				result += find(p)
		print(result)
	else:
		k = find(Y)
		left = Y - k * k
		if left > 700:
			print(k * 700)
		else:
			print(k * left + (k - 1) * (700 - left))


t = int(input())
for _ in range(t):
	y = int(input())
	q = 0
	w = int(y ** 0.5)
	if w ** 2 == y:
		if y > 700:
			lol = int((y - 700) ** 0.5)
			q = (w - 1) * w * (2 * w - 1) // 6 - lol * (lol + 1) * (2 * lol + 1) // 6
			a = y * (w - 1) - y * lol
			c = a - q + 700 * lol
		else:
			q = (w - 1) * w * (2 * w - 1) // 6
			a = y * (w - 1)
			c = a - q
	elif y > 700:
		lol = int((y - 700) ** 0.5)
		q = w * (w + 1) * (2 * w + 1) // 6 - lol * (lol + 1) * (2 * lol + 1) // 6
		a = y * w - y * lol
		c = a - q + 700 * lol
	else:
		q = w * (w + 1) * (2 * w + 1) // 6
		a = y * w
		c = a - q
	print(c)


import math
T = int(input())
for i in range(T):
	y = int(input())
	n = int(math.sqrt(y))
	ans = y * n - n * (n + 1) * (2 * n + 1) / 6
	t = 1
	if y > 700:
		xx1 = y - 700
		xx = int(math.sqrt(xx1))
		ans1 = xx1 - (xx + 1) * (2 * xx + 1) / 6
		ans1 = ans1 * xx
		ans = ans - ans1
		if ans - int(ans) > 0.5:
			ans = ans + 1
	print(int(ans))


import math
t = int(input())
a = [0] * 100001
for i in range(100001):
	a[i] = i * i
for i in range(t):
	y = int(input())
	x = 1
	L = []
	n = 1
	if y == 1:
		print(0)
		continue
	cnt = 0
	ind = int(math.sqrt(y - 1))
	for i in range(ind, 0, -1):
		if y - a[i] <= 700:
			cnt += y - a[i]
		else:
			cnt += 700 * i
			break
	print(cnt)


import math
a = [0] * 100001
for i in range(100001):
	a[i] = i * i
for _ in range(int(input())):
	n = int(input())
	ans = 0
	p = int(math.sqrt(n - 1))
	for i in range(p, 0, -1):
		m = n - a[i]
		if m <= 700:
			ans += m
		else:
			ans += 700 * i
			break
	print(ans)


from math import sqrt, floor

def sn(p):
	return p * (p + 1) * (2 * p + 1) // 6
for _ in range(int(input())):
	y = int(input())
	al = 0
	if y > 700:
		al = floor(sqrt(y - 700))
	ar = floor(sqrt(y - 1))
	ans = al * 700 + (ar - al) * y - (sn(ar) - sn(al))
	print(ans)


from math import sqrt, floor
for _ in range(int(input())):
	y = int(input())
	ans = 0
	if y >= 700:
		al = floor(sqrt(y - 700))
		ar = floor(sqrt(y - 1))
		ans = al * 700
		for i in range(al + 1, ar + 1):
			ans += y - i ** 2
	else:
		ar = floor(sqrt(y))
		for i in range(1, ar + 1):
			ans += y - i ** 2
	print(ans)


t = int(input())
for ijk in range(0, t):
	cnt = 0
	lmt = 0
	y = int(input())
	if y > 700:
		lmt = int((y - 700) ** 0.5)
	cnt += lmt * 700
	lmt += 1
	while lmt * lmt < y:
		cnt += y - lmt * lmt
		lmt += 1
	print(cnt)


import math
for t in range(int(input())):
	y = int(input())
	c = 0
	if y > 700:
		a = math.floor(math.sqrt(y - 700))
	else:
		a = 0
	b = math.floor(math.sqrt(y - 1))
	c += 700 * a
	a += 1
	for i in range(a, b + 1):
		c += min(700, y - i * i)
	print(c)


import math
for _ in range(int(input())):
	cnt = 0
	lmt = 0
	y = int(input())
	if y > 700:
		lmt = int((y - 700) ** 0.5)
	cnt += lmt * 700
	lmt += 1
	while lmt * lmt < y:
		cnt += y - lmt * lmt
		lmt += 1
	print(cnt)


for t in range(int(input())):
	y = int(input())
	c = 0
	a = 0
	if y > 700:
		a = pow(y - 700, 0.5)
		a = int(a)
		c = c + 700 * a
	for j in range(a + 1, y):
		if y - j * j <= 0:
			break
		else:
			c = c + (y - j * j)
	print(c)


import math
T = int(input())
for i in range(T):
	y = int(input())
	t = int(math.sqrt(y))
	temp = y - t * t
	ans = 0
	while temp < 700 and t > 0:
		ans += temp
		t -= 1
		temp = y - t * t
	ans = t * 700 + ans
	print(ans)


def solve(Y):
	l = int(Y ** 0.5)
	sq_l = l * (l + 1) * (2 * l + 1) // 6
	if Y <= 701:
		return l * Y - sq_l
	elif Y > 701:
		m = int((Y - 700) ** 0.5) + 1
		sq_m_1 = (m - 1) * m * (2 * m - 1) // 6
		return 700 * (m - 1) + (l - m + 1) * Y - (sq_l - sq_m_1)
for _ in range(int(input())):
	Y = int(input())
	print(solve(Y))


from math import sqrt, ceil, floor

def sq_sum(n):
	return n * (n + 1) * (2 * n + 1) / 6.0

def calculate_n(c):
	m = floor(sqrt(c - 1))
	k = ceil(sqrt(c - 700)) if c > 700 else 1
	n = int(c * (m - k + 1) - (sq_sum(m) - sq_sum(k - 1)) + 700 * (k - 1))
	return n

def main():
	n = int(input(''))
	for i in range(n):
		Y = int(input(''))
		print(calculate_n(Y))
main()


for t in range(int(input())):
	a = int(input())
	root = int(a ** 0.5)
	su = 0
	for i in range(root, 0, -1):
		if a - i ** 2 <= 700:
			su = su + (a - i ** 2)
		else:
			su = su + 700 * i
			break
	print(su)


t = int(input())
for _ in range(t):
	y = int(input())
	i = int(pow(y, 0.5))
	ans = 0
	while y - i * i <= 700 and i > 0:
		ans += y - i * i
		i -= 1
	ans += i * 700
	print(ans)


import math
T = int(input())
for _ in range(T):
	Y = int(input())
	X = math.floor((Y - 1) ** 0.5)
	Pairs = 0
	if Y > 700:
		Var = math.ceil((Y - 700) ** 0.5)
		Pairs += 700 * (Var - 1)
		Pairs += int((X - Var + 1) * Y - X * (X + 1) * (2 * X + 1) / 6 + Var * (Var - 1) * (2 * Var - 1) / 6)
	else:
		Pairs = int(X * Y - X * (X + 1) * (2 * X + 1) / 6)
	print(Pairs)


def my_range(start, end, step):
	while start <= end:
		yield start
		start += step
t = int(input())
while t > 0:
	n = int(input())
	k = 0
	if n > 700:
		p = n - 700
		g = int(p ** (1 / 2))
		k = g * 700
	else:
		g = 0
	for i in my_range(g + 1, n, 1):
		if i * i >= n:
			break
		k += n - i * i
	print(k)
	t -= 1


import math
tc = int(input())
for i in range(tc):
	y = int(input())
	count = 0
	k = int(math.sqrt(y - 1))
	while k > 0:
		if y - k * k > 700 or y - k * k <= 0:
			break
		count += y - k ** 2
		k -= 1
	count += k * 700
	print(count)


import math
t = int(input())
for x in range(t):
	y = int(input())
	pairs = 0
	maxA = int(math.sqrt(y))
	a = maxA
	while a >= 1:
		b = y - a * a
		if b <= 700:
			pairs += b
		else:
			pairs += a * 700
			break
		a -= 1
	print(pairs)


t = int(input())
for i in range(t):
	y = int(input())
	k = int(y ** 0.5)
	ans = 0
	while y - k * k <= 700 and k >= 1:
		ans += y - k * k
		k -= 1
	ans += k * 700
	print(ans)


t = int(input())
for _ in range(t):
	q = int(input())
	r = int(pow(q, 0.5))
	i = r
	c = 0
	while i > 0 and q - i * i < 700:
		c += q - i * i
		i -= 1
	if i > 0:
		c += 700 * i
	print(c)


import math
t = int(input())
for i in range(t):
	y = int(input())
	x = 0
	m = 0
	d = 0
	if y > 701:
		d = int(math.sqrt(y - 701))
		m = d * (d + 1) * (d * 2 + 1) // 6
		x = 700 * d
	c = int(math.sqrt(y))
	n = c * (c + 1) * (2 * c + 1) // 6
	z = y * (c - d)
	print(z - n + m + x)


def evaluate(n):
	m = n ** (1 / 2.0) - 1
	m = int(m)
	sum = 4 * m ** 3 + 9 * m ** 2 + 5 * m
	sum /= 6
	return sum
t = int(input())
for i in range(t):
	d = int(input())
	if d <= 1:
		print('0')
	elif d <= 700:
		d = d - 1
		if d == 1:
			print('1')
			continue
		x = int(evaluate(d))
		y = int(d ** (1 / 2.0))
		l = y * y
		o = d - l + 1
		x += o * y
		print(x)
	else:
		x = int(evaluate(d - 1))
		y = int((d - 1) ** (1 / 2.0))
		l = y * y
		o = d - 1 - l + 1
		x += o * y
		x2 = int(evaluate(d - 701))
		y2 = int((d - 701) ** (1 / 2.0))
		l2 = y2 * y2
		o2 = d - 701 - l2 + 1
		x2 += o2 * y2
		print(x - x2)


for _ in range(int(input())):
	n = int(input())
	a = 0
	count = 0
	if n > 701:
		a = int((n - 700) ** 0.5)
		count += a * 700
	while (a + 1) * (a + 1) < n:
		a += 1
		count += n - a * a
	print('%d' % count)


import math
tc = int(input())
while tc:
	y = int(input())
	ans = 0
	sqrtrest = 0
	if y > 700:
		rest = y - 700
		sqrtrest = int(math.sqrt(rest))
		ans += 700 * sqrtrest
	sqrty = int(math.sqrt(y))
	for i in range(sqrtrest + 1, sqrty + 1):
		add = y - i ** 2
		ans += add
	print(ans)
	tc -= 1


def sum_of_squares(n):
	return n * (n + 1) * (2 * n + 1) // 6
from math import sqrt
for _ in range(int(input().strip())):
	y = int(input())
	sq1 = int(sqrt(y - 1))
	diff = max(0, y - 700)
	sq2 = int(sqrt(diff))
	print(700 * sq2 + y * (sq1 - sq2) - (sum_of_squares(sq1) - sum_of_squares(sq2)))


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


for _ in range(int(input())):
	y = int(input())
	b = 700
	pair = 0
	if y <= 700:
		while True:
			if y >= b:
				approx = int((y - b) ** (1 / 2))
				pair += b * approx
				break
			b -= 1
	else:
		approx = int((y - b) ** (1 / 2))
		pair += b * approx
	k = 1
	while True:
		b = y - (approx + k) ** 2
		if b < 0:
			break
		pair += b
		k += 1
	print(pair)


import math

def main():
	t = int(input())
	while t > 0:
		n = int(input())
		count = 0
		sq = 1000000000000
		whole = 0
		for i in range(1, 701):
			if n - i > 0:
				if n - i > sq:
					count += whole
				else:
					temp = math.sqrt(n - i)
					whole = int(temp)
					sq = whole ** 2
					count += whole
			else:
				break
		print(count)
		t -= 1
main()


t = int(input())
for test in range(t):
	y = int(input())
	sqy = int(y ** 0.5)
	calc = 0
	while sqy > 0 and y - sqy * sqy <= 700:
		calc += y - sqy * sqy
		sqy -= 1
	calc += 700 * sqy
	print(calc)


import math
for _ in range(int(input())):
	y = int(input())
	c = 0
	q = 0
	if y > 700:
		q = int(pow(y - 700, 0.5))
	c = q * 700
	q += 1
	while q * q < y:
		c += y - q * q
		q += 1
	print(c)


t = int(input())
for _ in range(t):
	ans = 0
	y = int(input())
	x = y ** 0.5
	if x == int(x):
		a = int(x) - 1
	else:
		a = int(x)
	b = y - a ** 2
	while b <= 700 and a > 0:
		a = a - 1
		ans = ans + b
		b = y - a ** 2
	ans = ans + a * 700
	print(ans)


def main():
	T = int(input())
	for i in range(T):
		Y = int(input())
		cnt = 0
		temp = int((Y - 1) ** 0.5)
		if Y > 700:
			temp2 = int((Y - 700) ** 0.5)
		else:
			temp2 = 0
		cnt += temp2 * 700
		cnt += (temp - temp2) * Y
		cnt += int(temp2 * (temp2 + 1) * (temp2 * 2 + 1) // 6)
		cnt -= int(temp * (temp + 1) * (temp * 2 + 1) // 6)
		print(cnt)
main()


def func():
	Y = int(input())
	sum_num = 0
	m = int(Y ** (1 / 2))
	count = 0
	while Y - m ** 2 <= 700 and Y - m ** 2 >= 0 and (m > 0):
		count += Y - m ** 2
		m -= 1
	count += m * 700
	print(count)
t = int(input())
for i in range(t):
	func()


import math
t = int(input())
b = 700
for x in range(t):
	y = int(input())
	if y > 700:
		y1 = math.floor((y - b) ** 0.5)
		c = y1 * 700
	else:
		y1 = 0
		c = 0
	while y1 ** 2 + (1 + 2 * y1) < y:
		c = y - (y1 ** 2 + (1 + 2 * y1)) + c
		y1 = y1 + 1
	print(c)


import math

def main():
	T = int(input())
	for i in range(T):
		Y = int(input())
		cnt = 0
		temp = int(math.sqrt(Y - 1))
		j = temp
		while j > 0:
			if Y - j * j > 700 or Y - j * j < 0:
				break
			cnt += Y - j * j
			j -= 1
		cnt += j * 700
		print(cnt)
main()


import math

def sqp(n):
	return n * (n + 1) * (2 * n + 1) // 6
t = int(input())
while t != 0:
	y = int(input())
	ry = math.sqrt(y)
	fry = math.floor(ry)
	maxA = -1
	if ry == fry:
		maxA = fry - 1
	else:
		maxA = fry
	maxB = y - 1
	if maxB > 700:
		tm = math.sqrt(y - 700)
		tmf = math.floor(tm)
		mxtm = maxA - tmf
		print(tmf * 700 + mxtm * y - sqp(maxA) + sqp(tmf))
	else:
		print(maxA * y - sqp(maxA))
	t -= 1


from math import *
t = int(input())
ctr = 0
while t > ctr:
	y = int(input())
	ans = 0
	if y > 700:
		ans += int(sqrt(y - 700)) * 700
		a = int(sqrt(y - 700) + 1)
	else:
		a = 1
	while a ** 2 < y:
		ans += y - int(a * a)
		a += 1
	print(ans)
	ctr += 1


n = int(input().strip())
for i in range(n):
	cnt = 0
	k = int(input().strip())
	l = int(k ** 0.5)
	m = l
	while k - m ** 2 <= 700 and k - m ** 2 >= 0 and (m > 0):
		cnt += k - m ** 2
		m -= 1
	cnt += m * 700
	print(cnt)


for i in range(int(input())):
	c = 0
	n = int(input())
	if n <= 352 ** 2:
		for j in range(1, int(n ** 0.5) + 1):
			for k in range(700, 0, -1):
				if j ** 2 + k <= n:
					c += k
					break
		print(c)
	else:
		b = n ** 0.5
		if b == int(b):
			print(int(700 * (b - 1)))
		else:
			k = n - int(b) ** 2
			if k > 700:
				print(700 * int(b))
			else:
				print(700 * int(b) - 700 + k)


for _ in range(int(input())):
	y = int(input())
	p = 0
	if y <= 700:
		for b in range(1, 701):
			a = 1
			while a ** 2 + b <= y:
				p += 1
				a += 1
		print(p)
	if y > 700:
		Amax = int((y - 1) ** 0.5)
		Amid = int((y - 700) ** 0.5)
		p = Amid * 700
		for i in range(Amid + 1, Amax + 1):
			p += int(y - i ** 2)
		print(p)


from math import sqrt, floor
for tt in range(int(input())):
	a = int(input())
	l = floor(sqrt(max(0, a - 700)))
	h = floor(sqrt(a - 1))
	ans = 700 * l
	i = l + 1
	while i <= h:
		ans += a - i * i
		i += 1
	print(ans)


def fun(y):
	b = 1
	s = 0
	while b <= 700 and y > b:
		a = int((y - b) ** (1 / 2))
		b1 = y - a ** 2
		if b1 > 700:
			b1 = 700
		n = b1 - b + 1
		s = s + n * a
		b = b1 + 1
	return s
t = int(input())
y = []
for _ in range(t):
	y = int(input())
	print(fun(y))


for t in range(int(input())):
	Y = int(input())
	a = int(Y ** 0.5)
	aa = a * a
	ans = 0
	while Y - aa < 700 and a > 0:
		ans += Y - aa
		a -= 1
		aa = a * a
	if a > 0:
		ans += 700 * a
	print(ans)


import math
t = int(input())
for ind in range(t):
	y = int(input())
	firstsquareroot = int(math.sqrt(y))
	firstsquare = firstsquareroot * firstsquareroot
	result = 0
	if firstsquare + 700 <= y:
		result = firstsquareroot * 700
	else:
		while firstsquare > 0:
			if firstsquare + 700 <= y:
				result = result + firstsquareroot * 700
				break
			result = result + y - firstsquare
			firstsquareroot = firstsquareroot - 1
			firstsquare = firstsquareroot * firstsquareroot
	print(result)


from math import sqrt
t = int(input())
for x1 in range(t):
	y = int(input())
	ma = int(sqrt(y - 1))
	(c, mas) = (0, ma * ma)
	while ma != 0 and y - mas < 700:
		c += y - mas
		ma -= 1
		mas = ma * ma
	c += ma * 700
	print(c)


import math
for _ in range(int(input().strip())):
	y = int(input().strip())
	total = 0
	if y > 700:
		lower = math.ceil((y - 700) ** 0.5)
		total = 700 * (lower - 1)
	else:
		lower = 1
	upper = math.ceil(y ** 0.5)
	for i in range(lower, upper):
		total += y - i ** 2
	print(total)


import math
test = int(input())
for _ in range(test):
	n = int(input())
	l = int(math.sqrt(n))
	if n - 700 > 0:
		li = int(math.sqrt(n - 700))
		total = li * 700
	else:
		li = 0
		total = 0
	for i in range(li + 1, l + 1):
		temp = n - i ** 2
		total += temp
	print(total)


from math import sqrt, floor
T = int(input())
for _ in range(T):
	Y = int(input())
	solutions = 0
	if Y <= 1000:
		for B in range(1, min(701, Y)):
			A = 1
			while A ** 2 + B <= Y:
				solutions += 1
				A += 1
	elif Y > 1000:
		y = sqrt(Y - 1)
		y_ = sqrt(Y - 700)
		if floor(y) == floor(y_):
			solutions += floor(y) * 700
		else:
			for B in range(1, min(701, Y)):
				solutions += floor(sqrt(Y - B))
	print(solutions)


import math
squares = []
for i in range(1, 10 ** 5 + 1):
	squares.append(i * i)
t = int(input())
while t > 0:
	t -= 1
	y = int(input())
	y_root = math.floor(math.sqrt(y))
	val = 0
	for j in reversed(range(y_root)):
		if y - squares[j] > 700:
			val += (j + 1) * 700
			break
		else:
			val += y - squares[j]
	print(val)


import math
t = int(input())
for i in range(t):
	y = int(input())
	s = int(math.sqrt(y))
	if y > 701:
		x = y - 701
		w = int(math.sqrt(x))
		z1 = w * (w + 1) * (2 * w + 1) // 6
		z2 = s * (s + 1) * (2 * s + 1) // 6
		ans = w * 700 + (s - w) * y - (z2 - z1)
	else:
		z = s * (s + 1) * (2 * s + 1) // 6
		ans = s * y - z
	print(ans)


def f(y):
	j = int(y ** 0.5)
	ans = 700 * j
	while y - j * j < 700 and j >= 1:
		ans += -700 + y - j * j
		j -= 1
	return ans
t = int(input())
while t > 0:
	t = t - 1
	y = int(input())
	print(f(y))


import math
tc = int(input())
for etc in range(tc):
	T = int(input())
	x_min = 1
	c = 0
	if T >= 700:
		x_min = math.floor(math.sqrt(T - 700))
		c = 700 * x_min
		x_min += 1
	x_max = math.floor(math.sqrt(T))
	for x in range(x_min, x_max + 1):
		y = T - x ** 2
		c += min(700, y)
	print(c)


from math import floor, ceil
cases = int(input())
for _ in range(cases):
	y = int(input())
	c = floor(max(0, y - 700) ** 0.5) * 700
	x = floor(max(0, y - 700) ** 0.5) + 1
	for a in range(x, x + 50):
		if a ** 2 < y:
			c += y - a ** 2
	print(c)


MAX = 10 ** 5 + 1
Squares = []
for i in range(1, MAX + 2):
	Squares.append(i * i)
for _ in range(int(input())):
	Y = int(input())
	Ans = 0
	Beg = 0
	End = len(Squares) - 2
	Idx = -1
	YSub = Y - 700
	while Beg <= End:
		Mid = (Beg + End) // 2
		if Squares[Mid] <= YSub and Squares[Mid + 1] > YSub:
			Idx = Mid
			Ans = (Mid + 1) * 700
			break
		elif Squares[Mid] <= YSub and Squares[Mid + 1] <= YSub:
			Beg = Mid + 1
		else:
			End = Mid - 1
	for i in range(Idx + 1, len(Squares)):
		if Squares[i] > Y:
			break
		else:
			Ans += Y - Squares[i]
	print(Ans)


from math import sqrt, floor
t = int(input())
for a0 in range(t):
	y = int(input())
	minsq = floor(sqrt(y))
	count = 0
	while y - minsq ** 2 < 700:
		count += y - minsq ** 2
		minsq -= 1
		if minsq == 0:
			break
	if minsq != 0:
		count += minsq * 700
	print(count)


def fun():
	t = int(input())
	for a0 in range(t):
		n = int(input())
		k = int(n ** (1 / 2))
		tot = 0
		while k != 0 and n - k ** 2 < 700:
			tot = tot + (n - k ** 2)
			k = k - 1
		if n - k ** 2 >= 700:
			tot = tot + 700 * k
		print(tot)
fun()


for i in range(int(input())):
	n = int(input())
	x = int(n ** 0.5)
	if n > 700:
		y = int((n - 700) ** 0.5)
	if n <= 700:
		count = 0
		for j in range(1, int(n ** 0.5) + 1):
			if n - j ** 2 >= 0:
				count += n - j ** 2
	else:
		count = y * 700
		for j in range(y + 1, x + 2):
			if n - j ** 2 >= 0:
				count += n - j ** 2
	print(count)