题目描述

题目译自 XXIX Olimpiada Informatyczna – I etap 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。

4

5

101

NIE

样例 3

见附加文件下 [dom1.in](file:dom1.in) 和 [dom1.out](file:dom1.out)。

该样例满足 $m=9$，答案是 $n=7$。

样例 4

见附加文件下 [dom2.in](file:dom2.in) 和 [dom2.out](file:dom2.out)。

该样例满足 $m=11$，答案是 NIE。

样例 5

见附加文件下 [dom3.in](file:dom3.in) 和 [dom3.out](file:dom3.out)。

该样例满足 $m=500$，答案是 $n=20$。

样例 6

见附加文件下 [dom4.in](file:dom4.in) 和 [dom4.out](file:dom4.out)。

该样例满足 $m=112233445566778899$，答案是 NIE。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	答案不超过 $12$	$20$
$2$	$m \leq 2\cdot 10^6$	$30$
$3$	无附加限制	$50$