「POI 2021/2022 R1」Domino

题目描述

Bajtek 喜欢用尺寸为 $2 \times 1$ 的多米诺骨牌覆盖尺寸为 $2 \times n$ 的长方形。这个宽度为 $n$ 的长方形由 $2n$ 个尺寸为 $1 \times 1$ 的小方格组成，Bajtek 可以选择涂黑其中的一些小方格。他希望能够用多米诺骨牌覆盖所有未涂黑的小方格，而且骨牌之间不能重叠（骨牌可以旋转）。更进一步，Bajtek 想要确保恰好有 $m$ 种不同的覆盖方式。最后，他想找到能够达成这一目的的最小长方形。

下图展示了一个宽度为 $n=6$ 的长方形，其中两个小方格被涂黑了。有四种不同的方式用多米诺骨牌恰好覆盖剩下的 $10$ 个小方格。图中展示了两种覆盖方式：

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

编写一个程序，对于给定的 $m$，找出能够达到上述条件的最小长方形宽度 $n$。

输入格式

输入一行一个整数 $m$ $(1 \leq m \leq 10^{18})$。

输出格式

输出一行一个整数 $n$，表示所求长方形的最小可能宽度。如果不存在这样的长方形，输出 NIE。

样例

样例 1

输入:
4
输出:
5

样例 2

输入:
101
输出:
NIE

数据范围与提示