题目描述

有一个 $2$ 行 $n$ 列的矩形，上面有若干个格子被占用了。你要用 $1 \times 2$ 或 $2 \times 1$ 的牌，覆盖所有未被占用的格子，一个格子不可被占用两次。记方案数为 $m$。

给你 $m$，求出最小的 $n$，使得存在一种方案设置占用格，使得覆盖的方案数恰好为 $m$。无解输出 NIE。

输入格式

输入一行，一个正整数 $m$。

输出格式

如果有解，输出你的答案 $n$。

如果无解，输出 NIE。

样例输入 1

4

样例输出 1

5

样例输入 2

101

样例输出 2

NIE

样例输入 3

9

样例输出 3

7

样例输入 4

11

样例输出 4

NIE

样例输入 5

500

样例输出 5

20

样例输入 6

112233445566778899

样例输出 6

NIE

样例输入 7

1

样例输出 7

1

说明

数据范围

对于所有数据，$1 \le m \le 10^{18}$。

各测试点的附加限制如下表所示：

点击下载大样例