Kulyash loves perfect squares and hates perfect cubes.  
For any natural number N,  
F(N) = \texttt{number of perfect squares smaller than or equal to } N - \texttt{number of positive perfect cubes smaller than or equal to } N. 

Kulyash gives you an integer X and asks you to find the minimum value of N, such that F(N) ≥ X.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line of input.
- The first and only line of each test case contains an integer X.

------ Output Format ------ 

For each test case, output on a new line, the minimum value of N such that F(N) ≥ X.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ X ≤ 10^{9}$

----- Sample Input 1 ------ 
3
1
3
3151

----- Sample Output 1 ------ 
4
25
11397376

----- explanation 1 ------ 
Test case $1$: There are $2$ perfect squares from $1$ to $4$, and $1$ perfect cube from $1$ to $4$, so $F(4) = 2 - 1 = 1$, as required. 

Test case $2$: There are $5$ perfect squares from $1$ to $25$, and $2$ perfect cubes from $1$ to $25$, so $F(25) = 5 - 2 = 3$, as required. 

Test case $3$: There are $3376$ perfect squares from $1$ to $11397376$, and $225$ perfect cubes from $1$ to $11397376$, so $F(11397376) = 3376 - 225 = 3151$, as required.

Difficulty: HARD
Tags: Sorting

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
import math
t = int(input())
while t > 0:
	x = int(input())
	start = x
	end = 10 ** 10
	mid = (start + end) // 2
	ans = 10 ** 20
	while start <= end:
		sq = mid
		zz = mid * mid
		cb = int(zz ** (1 / 3))
		val = cb + 1
		val = val ** 3
		if val == zz:
			cb += 1
		dif = sq - cb
		if dif >= x:
			ans = min(ans, zz)
			end = mid - 1
			mid = (start + end) // 2
		else:
			start = mid + 1
			mid = (start + end) // 2
	print(ans)
	t -= 1


def find(n):
	start = 0
	end = 3000000
	while end - start > 1:
		mid = (start + end) // 2
		if mid * mid * mid > n:
			end = mid
		else:
			start = mid
	return start

def solve():
	x = int(input())
	num = x
	while num - find(num * num) < x:
		tmp = num * num
		cbs = find(tmp)
		num = x + cbs
	print(num * num)
T = int(input())
for _ in range(T):
	solve()


for _ in range(int(input())):
	x = int(input())
	n = x + int(x ** (2 / 3))
	while n - int(n ** (2 / 3)) != x:
		n += x - n + int(n ** (2 / 3))
	if (int(n ** (2 / 3)) + 1) ** 3 == n * n:
		print((n + 1) ** 2)
	else:
		print(n ** 2)


mod_ = 10 ** 9 + 7

def cbrts(n):
	(i, j) = (0, n)
	while i < j:
		x = (i + j) // 2
		if x * x * x <= n:
			i = x + 1
		else:
			j = x
	return i - 1
t = int(input())
for _ in range(t):
	x = int(input())
	n = x
	if x == 1:
		print(4)
		continue
	while True:
		diff = n - cbrts(n * n)
		if diff >= x:
			break
		n += x - diff
	print(n * n)


def cuberoot(num):
	x = int(num ** (1 / 3))
	x += 1
	while x * x * x > num:
		x -= 1
	return x
for _ in range(int(input())):
	x = int(input())
	(lo, hi) = (1, 2 * 10 ** 9)
	while lo < hi:
		mid = (lo + hi) // 2
		if mid - cuberoot(mid * mid + 1) >= x:
			hi = mid
		else:
			lo = mid + 1
	print(lo * lo)


def perfectCube(N):
	cube_root = round(N ** (1 / 3))
	if cube_root * cube_root * cube_root == N:
		return True
	else:
		return False
import math

def isPerfectSquare(x):
	if x >= 0:
		sr = int(math.sqrt(x))
		return sr * sr == x
for t in range(int(input())):
	x = int(input())
	l = 0
	r = 10000000000
	while r - l > 0:
		mid = (l + r) // 2
		if perfectCube(mid ** 2):
			y = round(pow(mid ** 2, 1 / 3))
		else:
			y = int(pow(mid ** 2, 1 / 3))
		ans = int(mid) - y
		if ans < x:
			l = mid + 1
		else:
			r = mid
	print(l ** 2)


import math
from numpy import cbrt
a = int(input())
for i in range(a):
	num = int(input())
	x = num
	while 1:
		cu = cbrt(x * x)
		if math.ceil(cu) * math.ceil(cu) * math.ceil(cu) == x * x:
			cu = math.ceil(cu)
		c = int(math.sqrt(x * x)) - int(cu)
		if c >= num:
			print(int(x * x))
			break
		else:
			x += num - c


from bisect import bisect_left
cubes = [i ** 3 for i in range(1, 1010000)]
for _ in range(int(input())):
	x = int(input())
	(lo, hi) = (1, 2 * 10 ** 9)

	def g(n):
		return n - bisect_left(cubes, n * n + 1)
	while lo < hi:
		mid = (lo + hi) // 2
		if g(mid) >= x:
			hi = mid
		else:
			lo = mid + 1
	print(lo * lo)


import math
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	l = 0
	r = 10 ** 10
	ans = -1
	while r >= l:
		mid = (r + l) // 2
		y = mid * mid
		e = y ** (1 / 3)
		e = int(e)
		w = e + 1
		w = w ** 3
		if w == y:
			e += 1
		if mid - e >= n:
			ans = mid * mid
			r = mid - 1
		else:
			l = mid + 1
	print(ans)


import sys
from os import path
import math
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def i():
	return int(input())

def s():
	return str(input())

def ii():
	return map(int, input().split())

def li():
	return list(input())

def lii():
	return list(map(int, input().split()))

def p(x):
	print(x)

def fip(x, s):
	for i in x:
		print(i, end=s)
	print()
for _ in range(int(input())):
	x = i()
	low = x
	high = 10 ** 10
	ans = 10 ** 20
	while low <= high:
		mid = (low + high) // 2
		s = mid ** 2
		cb = int(s ** (1 / 3))
		val = cb + 1
		val = val ** 3
		if val == s:
			cb += 1
		if mid - cb >= x:
			ans = min(ans, mid ** 2)
			high = mid - 1
		else:
			low = mid + 1
	print(ans)


for _ in range(int(input())):
	x = int(input())
	m = 0
	while True:
		y = int(m ** (2.0 / 3.0) + 2)
		while y ** 3 > m ** 2:
			y -= 1
		m1 = x + y
		if m1 == m:
			break
		m = m1
	print(m * m)


def square(n):
	val = int(pow(n, 0.5))
	if (val + 1) ** 2 <= n:
		return val + 1
	return val

def cube(n):
	val = int(pow(n, 1 / 3))
	if (val + 1) ** 3 <= n:
		return val + 1
	return val

def F(n):
	return square(n) - cube(n)

def solve(x):
	num = x
	ans = x ** 2
	fn = num - cube(ans)
	while fn < x:
		diff = x - fn
		num += diff
		ans = num ** 2
		fn = num - cube(ans)
	return ans
for case in range(int(input())):
	X = int(input())
	curAns = solve(X)
	print(curAns)


t = int(input())
import math
for i in range(t):
	x = int(input())
	l = int(x ** 0.66)
	r = int(x ** 0.7) + 2
	while l != r:
		mi = (l + r) // 2
		if (mi + 1) ** 1.5 - mi <= x:
			l = mi + 1
		else:
			r = mi
	print((l + x) ** 2)


import math
import bisect
import sys
sys.setrecursionlimit(10000)

def binsearch(a, b, x):
	mid = (a + b) // 2
	a1 = int((mid ** 2) ** (1 / 3))
	if (a1 + 1) ** 3 == mid ** 2:
		a1 += 1
	if a >= b:
		return a
	elif mid - a1 < x:
		return binsearch(mid + 1, b, x)
	else:
		return binsearch(a, mid - 1, x)
for _ in range(int(input())):
	n = int(input())
	mid = binsearch(0, 3 * n + 100000, n)
	b = int(mid ** (2 / 3))
	if (b + 1) ** 3 == mid ** 2:
		b += 1
	while mid - b != n:
		mid += 1
		b = int(mid ** (2 / 3))
		if (b + 1) ** 3 == mid ** 2:
			b += 1
	print(mid ** 2)


for _ in range(int(input())):
	X = int(input())
	x = pow(X, 2)
	y = int(pow(x, 1 / 3))
	dif = y
	z = X
	while dif > 0:
		z += dif
		x = pow(z, 2)
		y = int(pow(z, 2 / 3))
		if pow(y + 1, 3) - x < 1:
			y += 1
		dif = X - z + y
	print(x)


for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(4)
	else:
		st = n
		x = n * n
		p = 0
		s = 0
		while s < 10:
			i = int(x ** (1 / 3))
			n = n + i - p
			x = n * n
			if i ** 3 < x and x < (i + 1) ** 3:
				break
			if i == p:
				i = i + 1
				break
			p = i
			s += 1
		print((st + i) ** 2)


import sys, threading
import math
from os import path
from collections import deque, defaultdict, Counter
from bisect import *
from string import ascii_lowercase
from functools import cmp_to_key
from random import randint
from heapq import *
from array import array
from types import GeneratorType

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline
MAXN = 1123456

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

class mydict:

	def __init__(self, func=lambda : 0):
		self.random = randint(0, 1 << 32)
		self.default = func
		self.dict = {}

	def __getitem__(self, key):
		mykey = self.random ^ key
		if mykey not in self.dict:
			self.dict[mykey] = self.default()
		return self.dict[mykey]

	def get(self, key, default):
		mykey = self.random ^ key
		if mykey not in self.dict:
			return default
		return self.dict[mykey]

	def __setitem__(self, key, item):
		mykey = self.random ^ key
		self.dict[mykey] = item

	def getkeys(self):
		return [self.random ^ i for i in self.dict]

	def __str__(self):
		return f'{[(self.random ^ i, self.dict[i]) for i in self.dict]}'

def lcm(a, b):
	return a * b // math.gcd(a, b)

def mod(n):
	return n % 1000000007

def upper_bound(a, num):
	l = 0
	r = len(a) - 1
	ans = -1
	while l <= r:
		mid = (l + r) // 2
		if a[mid] >= num:
			ans = mid
			r = mid - 1
		else:
			l = mid + 1
	return ans

def croot(num):
	l = 0
	r = num
	ans = l
	while l <= r:
		mid = (l + r) // 2
		if mid * mid * mid == num:
			return mid
		if mid * mid * mid <= num:
			ans = mid
			l = mid + 1
		else:
			r = mid - 1
	return ans

def sqr(num):
	l = 0
	r = num
	ans = l
	while l <= r:
		mid = (l + r) // 2
		if mid * mid <= num:
			ans = mid
			l = mid + 1
		else:
			r = mid - 1
	return ans

def solve(t):
	x = readInts()
	l = x
	r = 2 * x
	ans = x
	while l <= r:
		mid = (l + r) // 2
		sq = mid * mid
		cu = int(math.pow(sq, 1 / 3))
		if (cu + 1) ** 3 == sq:
			cu += 1
		dif = mid - cu
		if dif >= x:
			r = mid - 1
			ans = sq
		else:
			l = mid + 1
	print(ans)

def main():
	t = 1
	if path.exists('/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/input.txt'):
		sys.stdin = open('/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/input.txt', 'r')
		sys.stdout = open('/Users/arijitbhaumik/Library/Application Support/Sublime Text/Packages/User/output.txt', 'w')
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


import string
from functools import lru_cache
import atexit, io
import sys
from math import log2
import math
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right, insort
from math import gcd
from math import sqrt
from collections import Counter, defaultdict
from heapq import heappush, heappop, heapify
import heapq

class FenwickTree:

	def __init__(self, n):
		self.farr = [0] * (n + 1)

	def prefixSum(self, idx):
		s = 0
		while idx > 0:
			s += self.farr[idx]
			idx -= idx & -idx
		return s

	def update(self, idx, val):
		while idx < len(self.farr):
			self.farr[idx] += val
			idx += idx & -idx

	def find(self, k):
		curr = 0
		ans = 0
		prevSum = 0
		for i in range(log2(n), -1, -1):
			if self.farr[curr + (i << i)] + prevSum < k:
				curr += 1 << i
				prevSum += self.farr[curr]
		return curr + 1

class Trie(object):

	def __init__(self):
		self.trie = {}

	def insert(self, word):
		t = self.trie
		for c in word:
			if c not in t:
				t[c] = {}
			t = t[c]
		t['-'] = True

	def search(self, word):
		t = self.trie
		for c in word:
			if c not in t:
				return False
			t = t[c]
		return '-' in t

	def startsWith(self, prefix):
		t = self.trie
		for c in prefix:
			if c not in t:
				return False
			t = t[c]
		return True

	def query(self, word):
		ans = 0
		t = self.trie
		for i in word:
			if i not in t:
				break
			ans += 1
			t = t[i]
		return ans

class FenvTree:

	def __init__(self, arr):
		arr.insert(0, 0)
		self.farr = [0]
		prefix = [0]
		for i in arr[1:]:
			prefix.append(prefix[-1] + i)
		for i in range(1, len(arr)):
			idash = i - (i & -i)
			self.farr.append(prefix[i] - prefix[idash])

	def query(self, l, r):
		return self.prefixSum(r) - self.prefixSum(l - 1)

	def prefixSum(self, idx):
		s = 0
		while idx > 0:
			s += self.farr[idx]
			idx -= idx & -idx
		return s

	def update(self, idx, val):
		while idx < len(self.farr):
			self.farr[idx] += val
			idx += idx & -idx

class DSU:

	def __init__(self, n):
		self.parent = []
		self.size = []
		for i in range(n + 1):
			self.parent.append(i)
			self.size.append(1)

	def union(self, u, v):
		pu = self.findPar(u)
		pv = self.findPar(v)
		if pu == pv:
			return
		if self.size[pu] < self.size[pv]:
			self.parent[pu] = pv
			self.size[pv] += self.size[pu]
		else:
			self.parent[pv] = pu
			self.size[pu] += self.size[pv]

	def unionByRank(self, u, v):
		pu = self.findPar(u)
		pv = self.findPar(v)
		if pu == pv:
			return
		if self.rank[pu] < self.rank[pv]:
			self.parent[pu] = pv
		elif self.rank[pv] < self.rank[pu]:
			self.parent[pv] = pu
		else:
			self.parent[pu] = pv
			self.rank[pv] += 1

	def findPar(self, node):
		if self.parent[node] == node:
			return node
		self.parent[node] = self.findPar(self.parent[node])
		return self.parent[node]

class info:

	def __init__(self, _open=0, _close=0, _full=0):
		self.open = _open
		self.close = _close
		self.full = _full

class SGTree:

	def __init__(self, n):
		self.seg = [0 for _ in range(4 * n)]

	def build(self, ind, low, high, arr):
		if low == high:
			self.seg[ind] = arr[low]
			return
		mid = (low + high) // 2
		self.build(2 * ind + 1, low, mid, arr)
		self.build(2 * ind + 2, mid + 1, high, arr)
		self.seg[ind] = min(self.seg[2 * ind + 1], self.seg[2 * ind + 2])

	def query(self, ind, low, high, l, r):
		if r < low or l > high:
			return sys.maxsize
		if low <= l and r >= high:
			return self.seg[ind]
		mid = low + high >> 1
		left = self.query(2 * ind + 1, 0, mid, l, r)
		right = self.query(2 * ind + 2, mid + 1, high, l, r)
		return min(left, right)

	def update(self, ind, low, high, i, val):
		if low == high:
			self.seg = val
			return
		mid = low + high >> 1
		if i <= mid:
			self.update(2 * ind + 1, low, mid, i, val)
		else:
			self.update(2 * ind + 1, mid + 1, high, i, val)
		self.seg[ind] = min(self.seg[2 * ind + 1], self.seg[2 * ind + 2])

def isPalindrome(s):
	i = 0
	j = len(s) - 1
	while i < j:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True

def IntList():
	return list(map(int, sys.stdin.readline().strip().split()))

def getInts():
	return map(int, sys.stdin.readline().strip().split())

def getStrs():
	return sys.stdin.readline().strip()

def StrList():
	list(sys.stdin.readline().strip())

def FloatList():
	lis = input().split()
	lis = list(map(float, lis))
	return lis

def SieveOfEratosthenes(n, isPrime):
	isPrime[0] = isPrime[1] = False
	for i in range(2, n + 1):
		isPrime[i] = True
	p = 2
	while p * p <= n:
		if isPrime[p]:
			i = p * p
			while i <= n:
				isPrime[i] = False
				i += p
		p += 1

def findPrimePair(n):
	isPrime = [0] * (n + 1)
	SieveOfEratosthenes(n, isPrime)
	for i in range(0, n):
		if isPrime[i] and isPrime[n - i]:
			print(i, n - i)
			return

def query(ind, low, high, l, r, seg):
	if r < low or l > high:
		return info()
	if low <= l and r >= high:
		return self.seg[ind]
	mid = low + high >> 1
	left = self.query(2 * ind + 1, 0, mid, l, r, seg)
	right = self.query(2 * ind + 2, mid + 1, high, l, r, seg)
	return merge(left, right)

def merge(left, right):
	ans = info()
	ans.full = left.full + right.full + min(left.open, right.close)
	ans.open = left.open + right.open + min(left.open, right.close)
	ans.close = left.close + right.close + min(left.open, right.close)
	return ans

def build(ind, low, high, s, seg):
	if low == high:
		seg[ind] = info(s[low] == '(', s[low] == ')', 0)
		return
	mid = (low + high) // 2
	build(2 * ind + 1, low, mid, s, seg)
	build(2 * ind + 2, mid + 1, high, s, seg)
	seg[ind] = merge(seg[2 * ind + 1], seg[2 * ind + 2])

def countN(lis):
	ans = 0
	cnt = 0
	for i in range(len(lis) - 1, -1, -1):
		if lis[i] == 0:
			cnt += 1
		else:
			ans += cnt
	return ans

class Pair:

	def __init__(self, x, y, gcd):
		self.x = x
		self.y = y
		self.gcd = gcd

def Euclidean(a, b):
	if b == 0:
		return Pair(1, 0, a)
	dash = Euclidean(b, a % b)
	return Pair(dash.y, dash.x - a // b * dash.y, dash.gcd)

def chineseRemainder(a1, n1, a2, n2):
	p = Euclidean(n1, n2)
	x = p.x
	gcd = p.gcd
	if (a1 - a2) % gcd:
		return -1
	k = (a1 - a2) // gcd
	a = a1 - n1 * (k * x % n2 // gcd)
	lcm = n1 * n2 // gcd
	if a < 0:
		a += lcm
	return a
mdd = 998244353

def ncr(n, k, md):
	mod = 998244353
	tab = [[0 for _ in range(k + 1)] for i in range(n + 1)]
	for i in range(1, len(tab)):
		tab[i][0] = 1
	for i in range(1, len(tab)):
		for j in range(1, min(i + 1, len(tab[0]))):
			if i == 1 and j == 1:
				tab[i][j] = 1
			else:
				tab[i][j] = (tab[i - 1][j] + tab[i - 1][j - 1]) % mod
	return tab

def repeat(i, j, arr):
	if i > j:
		return
	cnt1 = i
	cnt2 = j
	while cnt1 < cnt2:
		(arr[cnt1], arr[cnt2]) = (arr[cnt2], arr[cnt1])
		cnt1 += 1
		cnt2 -= 1
	if i - 1 >= 0:
		ele = arr[i - 1]
		if ele > 0:
			s = int(sqrt(ele - 1)) + 1
			first = s * s - ele
			repeat(first, i - 1, arr)
	return
spf = []

def makeSeive(n):
	for i in range(n + 1):
		spf.append(i)

def seive(n):
	s = int(sqrt(n + 1))
	for i in range(2, s + 1):
		if spf[i] == i:
			for j in range(i * i, n + 1, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = set()
	while x != 1:
		ret.add(spf[x])
		x = x // spf[x]
	return ret

def zFunc(patt, txt):
	st = patt + '#' + txt
	zArray = [0 for _ in range(len(st))]
	l = 0
	r = 0
	for i in range(1, len(st)):
		if r >= i:
			zArray[i] = min(r - i + 1, zArray[i - l])
		while i + zArray[i] < len(st) and st[zArray[i]] == st[zArray[i] + i]:
			zArray[i] += 1
		if zArray[i] + i - 1 > r:
			l = i
			r = i + zArray[i] - 1
	return zArray.count(len(patt))

def kmp(txt, patt):
	newString = patt + '#' + txt
	freqCount = 0
	freqArray = [0 for _ in range(len(newString))]
	i = 1
	length = 0
	while i < len(newString):
		if newString[i] == newString[length]:
			length += 1
			freqArray[i] = length
			i += 1
		elif length > 0:
			length = freqArray[length - 1]
		else:
			freqArray[i] = 0
			i += 1
	for i in freqArray:
		if i == len(patt):
			freqCount += 1
	return freqCount

def getLPS(s):
	st = '@#' + '#'.join(s) + '#&'
	c = 0
	r = 0
	lps = [0] * len(st)
	for i in range(1, len(st) - 1):
		mirror = c - (i - c)
		if i < r and mirror >= 0:
			lps[i] = min(lps[mirror], r - i)
		while st[i + lps[i] + 1] == st[i - lps[i] - 1]:
			lps[i] += 1
		if i + lps[i] > r:
			r = i + lps[i]
			c = i
	return max(lps)
fact = [1 for _ in range(100002)]
mod = 10 ** 9 + 7

def getFact(n):
	for i in range(1, n + 1):
		fact[i] = fact[i - 1] * i % mod

def getInv(word):
	num = math.factorial(len(word))
	for v in Counter(word).values():
		num = num * pow(math.factorial(v), mod - 2, mod) % mod
	return int(num) % (10 ** 9 + 7)

def subarrayXor(arr, n, m):
	HashTable = defaultdict(bool)
	HashTable[0] = 1
	count = 0
	curSum = 0
	for i in arr:
		curSum ^= i
		if HashTable[curSum ^ m]:
			count += HashTable[curSum ^ m]
		HashTable[curSum] += 1
	return count

def get2dPrefixSum(matrix, mid=0):
	n = len(matrix)
	m = len(matrix[0])
	prefix = [[0 for _ in range(m + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + matrix[i - 1][j - 1]
	return prefix

def get2dPrefixSumCnt(matrix, mid=0):
	n = len(matrix)
	m = len(matrix[0])
	prefix = [[0 for _ in range(m + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + matrix[i - 1][j - 1]
	return prefix

def getSumRange(r1, c1, r2, c2, prefix):
	cnt = prefix[r2][c2] - prefix[r2][c1 - 1] - prefix[r1 - 1][c2] + prefix[r1 - 1][c1 - 1]
	return cnt

def getPrefix(arr):
	prefix = [0]
	for i in arr:
		prefix.append(prefix[-1] + i)
	return prefix

def getInv(arr):
	cnt = 0
	ans = []
	for i in arr:
		ind = bisect_right(ans, i)
		cnt += len(ans) - ind
		insort(ans, i)
	return cnt
M = 10 ** 5

def getFactors(x):
	temp = []
	k = 1
	while k * k <= x:
		if x % k == 0:
			temp.append(k)
			if k * k != x:
				temp.append(x // k)
		k += 1
	return temp

def grayCode(n):
	if not n:
		return [0]
	res = [0, 1]
	for i in range(2, n + 1):
		for j in range(len(res) - 1, -1, -1):
			res.append(res[j] | 1 << i - 1)
	return res

def threeSum(nums, target):
	ans = -1
	d = dict()
	for (i, j) in enumerate(nums):
		d[j] = i + 1
	nums.sort()
	for i in range(len(nums) - 2):
		low = i + 1
		high = len(nums) - 1
		while low < high:
			s = nums[i] + nums[low] + nums[high]
			if s == target:
				print(d[nums[low]], d[nums[high]], d[nums[i]])
				return
				low += 1
				high -= 1
			elif s < 0:
				low = low + 1
			else:
				high -= 1
	print('IMPOSSIBLE')
	return

def FuckCF():
	n = int(input())

	def solve(x):
		low = 0
		high = 10 ** 8
		while low + 1 < high:
			mid = (low + high) // 2
			cube = mid * mid * mid
			if cube > x:
				high = mid
			else:
				low = mid
		return low
	val = n
	sqr = val * val
	while val - solve(sqr) < n:
		sqr = val * val
		val = n + solve(sqr)
		sqr = val * val
	print(val * val)
t = 1
t = int(input())
for i in range(t):
	FuckCF()


def find(n):
	l = 0
	r = 3 * 10 ** 6
	while r - l > 1:
		mid = (l + r) // 2
		if mid ** 3 > n:
			r = mid
		else:
			l = mid
	return l

def main():
	x = int(input())
	n = x
	while n - find(n ** 2) < x:
		curr = n ** 2
		cr = find(curr)
		n = x + cr
	return n ** 2
for _ in range(int(input())):
	print(main())


import math

def find(n):
	s = 0
	e = int(3000000.0)
	while e - s > 1:
		mid = (s + e) // 2
		if mid ** 3 > n:
			e = mid
		else:
			s = mid
	return s
for _ in range(int(input())):
	x = int(input())
	n = x
	while n - find(n * n) < x:
		square = n * n
		cube = find(square)
		n = x + cube
	print(n * n)


import math

def solution(x):
	n = x
	count = x - math.floor(math.pow(n ** 2, 1 / 3))
	while count < x and count > -2:
		inc = x - count
		n += inc
		cubes = math.ceil(math.pow(n ** 2, 1 / 3))
		if cubes ** 3 > n ** 2:
			cubes -= 1
		count = n - cubes
	return n ** 2

def main():
	cases = int(input())
	for _ in range(cases):
		x = int(input())
		ans = solution(x)
		print(ans)
main()


import math

def countCubes(n):
	l = 1
	r = 1000000000
	while r > l + 1:
		mid = (l + r) // 2
		val = mid * mid * mid
		if val > n:
			r = mid
		else:
			l = mid
	return l

def CountSquares(a, b):
	return math.floor(math.sqrt(b)) - math.ceil(math.sqrt(a)) + 1
for _ in range(int(input())):
	n = int(input())
	c = n
	while c - countCubes(c * c) < n:
		val = c * c
		c = n + countCubes(val)
	print(c * c)


def check(k, x):
	return (k - x + 1) ** 3 > k ** 2

def solve():
	l = 0
	r = 100000000000
	x = int(input())
	while l < r:
		m = (l + r) // 2
		if check(m, x):
			r = m
		else:
			l = m + 1
	print(l * l)
T = int(input())
for t in range(0, T):
	solve()


def find_largest_y(n):
	(lower_bound, upper_bound) = (0, int(3000000.0))
	while upper_bound - lower_bound > 1:
		middle = (lower_bound + upper_bound) // 2
		if middle * middle * middle > n:
			upper_bound = middle
		else:
			lower_bound = middle
	return lower_bound

def solve_problem():
	input_num = int(input())
	current_num = input_num
	while current_num - find_largest_y(current_num * current_num) < input_num:
		current_squared = current_num * current_num
		current_best_y = find_largest_y(current_squared)
		current_num = input_num + current_best_y
	print(current_num * current_num)
num_test_cases = int(input())
for i in range(num_test_cases):
	solve_problem()


from math import isqrt

def find(n):
	(s, e) = (0, 3000000)
	while e - s > 1:
		mm = (s + e) // 2
		if mm * mm * mm > n:
			e = mm
		else:
			s = mm
	return s

def solve():
	x = int(input())
	nn = x
	while nn - find(nn * nn) < x:
		tmp = nn * nn
		cbs = find(tmp)
		nn = x + cbs
	print(nn * nn)
T = int(input())
for _ in range(T):
	solve()


import math
import random
import statistics
import operator
import itertools
import sys
import copy
from collections import defaultdict, Counter, deque, OrderedDict
from heapq import heapify, heappush, heappop
from functools import lru_cache, reduce
from bisect import bisect_left, bisect_right
KPMOD1 = 1000000007
KPMOD2 = 998244353

def modinverse(a, mod):
	return binpow(a, mod - 2)

def mult(a, b):
	return a % KPMOD1 * (b % KPMOD1) % KPMOD1

def add(a, b):
	return (a % KPMOD1 + b % KPMOD1) % KPMOD1

def binpow(a, b):
	if b == 0:
		return 1
	res = binpow(a, b // 2) % KPMOD1
	if b % 2:
		return res * res * a % KPMOD1
	else:
		return res * res % KPMOD1

def fact(a):
	if a == 0 or a == 1:
		return 1
	return a * (fact(a) % KPMOD1) % KPMOD1

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
MAX = 100
fact = [1] * MAX
invfact = [1] * MAX
for i in range(1, MAX):
	fact[i] = fact[i - 1] * i % KPMOD1
	invfact[i] = invfact[i - 1] * modinverse(i, KPMOD1) % KPMOD1

def factors(n):
	if n == 0:
		return set()
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def findans(val):
	(KPS, KPE) = (0, 3000000)
	while KPE - KPS > 1:
		KPM = (KPS + KPE) // 2
		if KPM * KPM * KPM > val:
			KPE = KPM
		else:
			KPS = KPM
	return KPS
for _ in range(int(input())):
	KPN = int(input())
	KPX = KPN
	while KPX - findans(KPX * KPX) < KPN:
		KPT = KPX * KPX
		KPC = findans(KPT)
		KPX = KPN + KPC
	print(KPX * KPX)


import math
t = int(input())
for i in range(0, t):
	n = int(input())
	res = n
	num = res - int(1e-07 + math.pow(res, 2 / 3))
	l = 1000
	while num != n and l > 0:
		l -= 1
		num = res - int(1e-07 + math.pow(res, 2 / 3))
		if num < n:
			res += n - num
		elif num > n:
			res -= n - num
	while res - 1 - int(1e-07 + math.pow(res - 1, 2 / 3)) == n:
		res -= 1
	print(res ** 2)


from typing import List

def find(n: int) -> int:
	start = 0
	end = 3000000
	while end - start > 1:
		mid = (start + end) // 2
		if mid * mid * mid > n:
			end = mid
		else:
			start = mid
	return start

def solve() -> None:
	x = int(input())
	num = x
	while num - find(num * num) < x:
		tmp = num * num
		cbs = find(tmp)
		num = x + cbs
	print(num * num)
T = int(input())
while T > 0:
	solve()
	T -= 1


import math

def binarytemp(n):
	l = 0
	r = 3 * 10 ** 6
	while r - l > 1:
		mid = (r + l) // 2
		if mid ** 3 <= n:
			l = mid
		else:
			r = mid
	return l

def s1():
	n = int(input())
	a = list(range(1, n // 2 + 1))[::-1]
	b = list(range(n // 2 + 1, n + 1))
	a.extend(b)
	print(*a)

def haikuru():
	(n, m, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	for ele in arr:
		stringfortester = ''
		listerposter = []
		parsertomorrow = 0
		while parsertomorrow < n:
			if ele > parsertomorrow:
				ele -= parsertomorrow + 1
			else:
				break
			parsertomorrow += 1
		print(1, parsertomorrow)
		while parsertomorrow >= 1:
			listerposter.append(min(ele // parsertomorrow, m - 1))
			ele -= listerposter[-1] * parsertomorrow
			parsertomorrow -= 1
		for i in listerposter[::-1]:
			stringfortester += str(i + 1) + ' '
		print(stringfortester)
tres = int(input())
for _ in range(tres):
	x = int(input())
	n = x
	while n - binarytemp(n ** 2) < x:
		heck = binarytemp(n ** 2)
		n = x + heck
	print(n ** 2)


from bisect import bisect_left, bisect_right
from collections import defaultdict
from math import floor
import time
cub = []
for x in range(1, 1100000):
	cub.append(x ** 3)
fun = lambda x: x - bisect_right(cub, x * x)
for cc in range(int(input())):
	x = int(input())
	(left, right) = (1, 10 ** 10)
	while left < right:
		mid = (left + right) // 2
		if x <= fun(mid):
			right = mid
		else:
			left = mid + 1
	print(left * left)


def find_cube_root(n):
	a = 0
	b = 3 * 10 ** 6
	while b - a > 1:
		m = (a + b) // 2
		if m ** 3 > n:
			b = m
		else:
			a = m
	return a
num_tests = int(input())
for i in range(num_tests):
	x = int(input())
	num = x
	while num - find_cube_root(num * num) < x:
		tmp = num * num
		cbrt = find_cube_root(tmp)
		num = x + cbrt
	print(num * num)


def find(n):
	(s, e) = (0, 3000000)
	while e - s > 1:
		m = (s + e) // 2
		if m ** 3 > n:
			e = m
		else:
			s = m
	return s

def solve():
	num = int(input())
	num1 = num
	while num1 - find(num1 ** 2) < num:
		temp = num1 ** 2
		cbs = find(temp)
		num1 = num + cbs
	print(num1 ** 2)
T = int(input())
for _ in range(T):
	solve()


import numpy as np
import math

def cuberoot(p):
	ans = p ** (1 / 3)
	x = round(ans)
	if x * x * x == p:
		return x
	else:
		return ans
t = int(input())
while t != 0:
	x = int(input())
	r = 10000000000
	l = 1
	ans = 0
	while l <= r:
		mid = (l + r) // 2
		sq = mid * mid
		sc = mid
		cc = math.floor(cuberoot(sq))
		dif = sc - cc
		if dif >= x:
			ans = mid
			r = mid - 1
		else:
			l = mid + 1
	print(ans * ans)
	t = t - 1


import math

def find_cube_root(n):
	start = 0
	end = 10000000
	while end - start > 1:
		mid = (start + end) // 2
		if mid ** 3 > n:
			end = mid
		else:
			start = mid
	return start
t = int(input())
while t:
	x = int(input())
	num = x
	while num - find_cube_root(num ** 2) < x:
		tmp = num ** 2
		cbrt = find_cube_root(tmp)
		num = x + cbrt
	print(num ** 2)
	t -= 1


from math import *
t = int(input())
for _ in range(t):
	x = int(input())
	c = x
	while True:
		n = c ** 2
		a = floor((n / 1) ** (1 / 3))
		if (a + 1) * (a + 1) * (a + 1) <= n:
			a += 1
		if c - a >= x:
			print(n)
			break
		c += x + a - c


from sys import stdin, stdout
from math import log, exp, sqrt, ceil
input = stdin.readline
r_int = lambda : int(input())
m_int = lambda : map(int, input().split())
l_int = lambda : list(map(int, input().split()))

def cbrt(x):
	return exp(log(x) / 3)

def solve():
	x = r_int()
	a = x - 1
	z = cbrt(13.5 * a + 1.5 * sqrt(3) * sqrt(a * (27 * a + 4)) + 1)
	v = (z + 1 / z + 1) / 3
	r = ceil(v ** 3)
	if r == round(cbrt(r)) ** 3:
		r += 1
	print(r * r)

def main():
	n_cases = r_int()
	for _ in range(n_cases):
		solve()
main()


t = int(input())
for i in range(t):
	x = int(input())
	a = x
	n = x ** 2
	while int(round(n ** 0.5, 5)) - int(round(n ** (1 / 3), 5)) < x:
		a = x + int(round(n ** (1 / 3), 5))
		n = a ** 2
	if a - 1 - (a - 1) ** (2 / 3) == x:
		n = (a - 1) ** 2
	print(n)


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

def fn(n):
	a = floor((n + 0.6) ** 0.5)
	b = floor((n + 0.7) ** (1 / 3))
	return a - b
for i in range(t):
	n = int(input())
	start = 1
	end = 10 ** 10
	while start < end:
		mid = (start + end) // 2
		mid1 = mid ** 2
		if fn(mid1) >= n:
			end = mid
		else:
			start = mid + 1
	print(start ** 2)


def i23(v):
	y = int(v ** (2.0 / 3.0) + 2)
	while y ** 3 > v ** 2:
		y -= 1
	return y

def II():
	return int(input())
for _ in range(int(input())):
	x = II()
	m = 0
	while True:
		m1 = x + i23(m)
		if m1 == m:
			break
		m = m1
	print(m * m)