Description

A 先生发明了一个小游戏。游戏有 N 根柱子和很多球。球被编号为 1、2、3„，球看上去很普通，但它们实际上是有魔法的。如果上下相邻的放在一起的两个球编号之和不是平方数，他们将以一个强大的力量相互排斥，不能放在一起。

玩家每一次拿一颗球放在其中一根柱子上（从上往下放），玩家拿球按照 1 号，2 号，3 号......这样的次序依次下去。你的任务是帮忙编程计算在 N 根柱子上最多可以放多少个球，注意当一根柱子上相邻的两个球编号之和不是平方数时是不能放在一起的。上图给出了四根柱子的最佳放法。

Input Format

输入一行一个整数 N ,表示柱子数量。

Output Format

输出一行，一个整数，表示最多可以放的球的数量，如果可以放无限多的球，请输出“-1”。

样例 1

4

11

样例 2

25

337

Hint

【数据规模】 对于 50%的数据： 1≤N≤50； 对于 100%的数据：1≤N≤5,000；