Bajtek 正在玩用 $2 \times 1$ 的多米诺骨牌覆盖 $2 \times n$ 矩形的游戏。宽度为 $n$ 的矩形由 $2n$ 个 $1 \times 1$ 的方格组成，其中一些方格可以被 Bajtek 涂色。Bajtek 希望在不重叠的情况下，用多米诺骨牌覆盖所有未涂色的方格（骨牌可以旋转）。此外，Bajtek 希望这种覆盖方式恰好有 $m$ 种。最后，他想找到能满足此条件的最小矩形。要求很多，你能帮帮他吗？

下图展示了一个宽度为 $n = 6$ 的矩形，其中有两个方格被涂色。剩下的 $10$ 个方格恰好有 $4$ 种多米诺骨牌覆盖方式。图中展示了其中的两种（为了更好地展示情况，多米诺骨牌被稍微缩小了）：

然而，这对于 $m = 4$ 来说并不是最优解，因为存在一个 $n = 5$ 的解。

请编写一个程序，对于给定的 $m$，求出满足以下条件的最小矩形宽度 $n$：可以通过涂色某些方格，使得剩余方格恰好有 $m$ 种 $2 \times 1$ 多米诺骨牌覆盖方式。

输入格式

输入的第一行也是唯一一行包含一个自然数 $m$ ($1 \le m \le 10^{18}$)。

输出格式

输出的第一行也是唯一一行应包含一个自然数 $n$，表示所求矩形的最小可能宽度。如果不存在这样的矩形，则输出单词 NIE。

样例

样例输入 1

4

样例输出 1

5

样例输入 2

101

样例输出 2

NIE

说明

测试用例： 1. $m = 9$，结果为 $n = 7$； 2. $m = 11$，结果为 NIE； 3. $m = 500$，结果为 $n = 20$； 4. $m = 112233445566778899$，结果为 NIE。

子任务

测试集分为以下子任务。每个子任务由一组或多组独立的测试用例组成。