Pak Chanek plans to build a garage. He wants the garage to consist of a square and a right triangle that are arranged like the following illustration.

Define $a$ and $b$ as the lengths of two of the sides in the right triangle as shown in the illustration. An integer $x$ is suitable if and only if we can construct a garage with assigning positive integer values for the lengths $a$ and $b$ ($a<b$) so that the area of the square at the bottom is exactly $x$. As a good friend of Pak Chanek, you are asked to help him find the $N$-th smallest suitable number.


-----Input-----

The only line contains a single integer $N$ ($1 \leq N \leq 10^9$).


-----Output-----

An integer that represents the $N$-th smallest suitable number.


-----Examples-----

Input
3
Output
7


-----Note-----

The $3$-rd smallest suitable number is $7$. A square area of $7$ can be obtained by assigning $a=3$ and $b=4$.

Difficulty: MEDIUM
Tags: Geometry

Sorting

Mathematics
Skill types: Sorting

Starter code:

Solutions:
N = int(input())
if N == 1:
	print(3)
elif N == 2:
	print(5)
elif N % 3 == 1:
	print(4 + 4 * (N // 3))
elif N % 3 == 2:
	print(5 + 4 * (N // 3))
elif N % 3 == 0:
	print(3 + 4 * (N // 3))


n = int(input())
if n == 1:
	print(3)
else:
	print(4 + (4 * n - 3) // 3)


[print(4 + (4 * n - 3) // 3 if n != 1 else 3) for n in [int(input())]]


n = int(input())
if n == 1:
	print(3)
elif n == 2:
	print(5)
elif n == 3:
	print(7)
else:
	print((n - 3) // 3 * 4 + (n - 3) % 3 + 7)


hain = int(input())
sober = hain // 3
lame = 3 if hain == 1 else sober * 4 + hain % 3 + 3
print(lame)


def f(x):
	ans = max((x - 1) // 2, 0)
	ans += max(0, (x - 4) // 4)
	return ans

def binsearch(n):
	low = 1
	flag = 0
	high = 10 ** 20
	while low <= high:
		mid = (low + high) // 2
		a = f(mid)
		if a == n:
			for x in range(mid - 10, mid + 10):
				if f(x) == n:
					print(x)
					flag = 1
					break
			if flag == 1:
				break
		elif a > n:
			high = mid - 1
		else:
			low = mid + 1
n = int(input())
binsearch(n)


n = int(input())

def cal(n):
	if n == 1:
		return 3
	if n == 2:
		return 5
	if n == 3:
		return 7
	a = ((n - 1) // 3 + 1) * 4
	if (n - 1) % 3 == 1:
		a += 1
	elif (n - 1) % 3 == 2:
		a += 3
	return a
print(cal(n))


n = int(input())
if n == 1:
	print(3)
elif n == 2:
	print(5)
elif n == 3:
	print(7)
elif n == 4:
	print(8)
else:
	s = 8
	n -= 4
	r = n % 3
	n = n // 3
	s += n * 4
	if r == 1:
		s += 1
	elif r == 2:
		s += 3
	print(s)


sequence = int(input())
if sequence == 1:
	print(3)
elif sequence == 2:
	print(5)
else:
	first_one_in_your_group = (int((sequence - 3) / 6) + 1) * 8 - 1
	ranking = int(sequence - 3) % 6
	if ranking == 0:
		print(first_one_in_your_group)
	elif ranking == 1:
		print(first_one_in_your_group + 1)
	elif ranking == 2:
		print(first_one_in_your_group + 2)
	elif ranking == 3:
		print(first_one_in_your_group + 4)
	elif ranking == 4:
		print(first_one_in_your_group + 5)
	else:
		print(first_one_in_your_group + 6)


n = int(input())
m = n // 3
x = 3 if n == 1 else m * 4 + n % 3 + 3
print(x)


n = int(input())
x = (n - 1) // 3
if n == 1:
	print(3)
elif (n - 1) % 3:
	print(2 * (n - x) + 1)
else:
	print(4 * (x + 1))


def area1(num):
	num = num - 1
	if num == 0:
		return 3
	elif num == 1:
		return 5
	elif num == 2:
		return 7
	elif num % 3 == 0:
		return 8 + 4 * int(num / 3 - 1)
	elif num % 3 == 1:
		div = int(num / 3)
		final = 8 + 4 * (div - 1) + 1
		return final
	else:
		div = int(num / 3)
		final = 8 + 4 * (div - 1) + 3
		return final
number = int(input())
print(area1(number))


n = int(input())
if n <= 5:
	print([3, 5, 7, 8, 9][n - 1])
else:
	(a, b) = ((n - 6) // 15, (n - 6) % 15)
	print((2 * a + 1 + (b > 6)) * 10 + [1, 2, 3, 5, 6, 7, 9, 0, 1, 3, 4, 5, 7, 8, 9][b])


n = int(input())
b = 1
a = 0
if n % 3 == 1 and n != 1:
	d = n // 3
	c = 8 + (d - 1) * 4
	print(c)
elif n != 1 and n != 2 and (n != 3):
	e = (n - 1) % 3
	d = (n - e) // 3
	c = 8 + (d - 1) * 4
	if e == 1:
		print(c + e)
	elif e == 2:
		print(c + e + 1)
elif n == 1 or n == 2 or n == 3:
	print((b + n) ** 2 - (a + n) ** 2)


N = int(input())
print(3 + 4 * (N // 3) + N % 3 if not N == 1 else 3)


a = int(input())
x = (a - 1) // 3
if a == 1:
	print(3)
elif (a - 1) % 3:
	print(2 * (a - x) + 1)
else:
	print(4 * (x + 1))


n = int(input())
if n == 1:
	print(3)
elif (n - 1) % 3 == 0:
	o = int((n - 1) / 3)
	print(4 * o + 4)
else:
	o = int((n - 1) / 3)
	oo = n - o
	ooo = oo + 1
	print(ooo * ooo - oo * oo)


def ctle(x):
	ct = 0
	for b in [1, 2]:
		jump = (x - b * b) // (2 * b)
		if jump <= 0:
			break
		ct += jump
	return ct
n = int(input())
lo = 1
hi = int(100000000000000.0)
while lo < hi:
	m = (lo + hi) // 2
	if ctle(m) >= n:
		hi = m - 1
	else:
		lo = m + 1
if ctle(lo - 1) >= n:
	lo -= 1
if ctle(lo) < n:
	lo += 1
print(lo)


def main():
	n = int(input())
	x = divmod(n, 3)
	print(3 if n == 1 else x[0] * 4 + x[1] + 3)
main()


n = int(input())
if n == 1:
	print(3)
else:
	n -= 1
	(a, b) = (n // 3, n % 3)
	ans = 4 * (a + 1)
	if b == 1:
		ans += 1
	elif b == 2:
		ans += 3
	print(ans)


n = int(input())
if n == 1:
	print(3)
	exit()
a = (n - 1) // 3 + 1
b = n % 3
if b == 0:
	print(4 * a + 3)
elif b == 1:
	print(4 * a)
else:
	print(4 * a + 1)


n = int(input())
l = 0
r = 3 * n
c = 0
d = 0
while l <= r:
	mid = (l + r) // 2
	val1 = 0
	if mid >= 8:
		val1 = mid // 4 - 1
	val2 = 0
	if mid >= 3:
		val2 = (mid - (1 - mid % 2)) // 2
	if val1 + val2 <= n:
		l = mid + 1
		c = val1
		d = val2
	else:
		r = mid - 1
if n == 1:
	print(3)
else:
	print(max(c * 4 + 4, d * 2 + 1))


NKK = int(input())
print(3 + 4 * (NKK // 3) + NKK % 3 if not NKK == 1 else 3)


n = int(input())
m = n // 3
l = 3 if n == 1 else m * 4 + n % 3 + 3
print(l)


n = int(input())
if n == 1:
	print(3)
else:
	k = ((n - 1) // 3 + 1) * 4
	if (n - 1) % 3 == 1:
		k += 1
	if (n - 1) % 3 == 2:
		k += 3
	print(k)


N = int(input())
import math
if N == 1:
	print(3)
if N == 2:
	print(5)
if N > 2:
	print(math.floor(4 * N / 3 + 3))


rang = int(input())
if rang == 1:
	print(3)
else:
	print(rang * 4 // 3 + 3)