<<Previous

Next>>

NKPC竞赛的选手们都很爱吃糖葫芦:-)。比赛之余，他们发明了一种“糖葫芦游戏”，规则如下：在桌上有n根棍子，假设这些棍子的长度均为无限长。现在我们有无穷多的山楂，所有的山楂被标号为1,2,3...
现在，要求你把山楂插到棍子上。规则是：按照山楂号码的先后顺序，先插1号山楂，然后插2号，再插3号……山楂一插到棍子上，就会落到棍子底端最上面的一颗山楂上面（若棍子上一颗山楂都没有则落到桌面上）。你在插每颗山楂时，可以由你决定插到哪根柱子上，但是必须满足一个条件：在同一个柱子上，上下挨者的两颗山楂上的号码之和必须是一个完全平方数（即它的平方根是一个正整数）。山楂一插入棍子就不允许再拔出来。

现在，我们的问题是，在桌上有n根棍子的情况下，你最多插多少颗山楂？

Input

输入只有一个正整数n(1<=n<=50),是棍子的根数

Output

输出只有一个正整数，最多能插到n根棍子上的山楂的个数。

Sample Input

4

Sample Output

11

Source

NKPC

Best User : Fliger

If the buttons do not work well , you may try Submit , Status , Post , 35 post(s), Back .

Editor : wysuperfly | Last update : wysuperfly | History

Update history:wysuperfly,wysuperfly,wysuperfly,wysuperfly