Pak Chanek 计划建造一个车库。他希望车库由一个正方形和一个直角三角形组成,排列如下图所示。
将 $$$a$$$ 和 $$$b$$$ 定义为直角三角形中两条边的长度,如图所示。整数 $$$x$$$ 是合适的,当且仅当我们可以构造一个车库,并为长度 $$$a$$$ 和 $$$b$$$ ($$$a<b$$$) 分配正整数值,使得底部正方形的面积恰好为 $$$x$$$。作为 Pak Chanek 的好朋友,您被要求帮助他找到第 $$$N$$$ 个最小的合适数字。
输入
唯一一行包含单个整数 $$$N$$$ ($$$1 \leq N \leq 10^9$$$)。
输出
一个整数,表示第 $$$N$$$ 个最小的合适数字。
示例
输入 #1
3
输出 #1
7
注意
$$$3$$$-rd 最小的合适数字是 $$$7$$$。通过指定 $$$a=3$$$ 和 $$$b=4$$$ 可以获得 $$$7$$$ 的正方形面积。