Description

有编号为 1,2,3,……,n-1,n 的球各一个, 现有若干根柱子,把所有球放入柱子 放入球的顺序必须是1,2,3,……,n-1,n,且每次只能在某根柱子最上面放球, 同一根柱子中,相邻两个球的编号之和必须为平方数 问最少需要几根柱子 如 n = 11 则至少需要4根柱子 10 6 9 11 3 7 5 1 2 4 8

Input

文件是多case的,每行一个整数 n ( 1 <= n <=1000),当 n 为 0 时输入结束

Output

每个case输出一行,为最少需要的柱子数

Sample Input

11 0

Sample Output

4

Author

windy7926778