题目描述
There are many interesting variations on the Tower of Hanoi problem. This version consists of N pegs and one ball containing each number from 1, 2, 3,…,. Whenever the sum of the numbers on two balls is not a perfect square (i.e., c2 for some integer c), they will repel each other with such force that they can never touch each other.
The player must place balls on the pegs one by one, in order of increasing ball number (i.e., first ball 1, then ball 2, then ball 3…). The game ends where there is no non-repelling move.
The goal is to place as many balls on the pegs as possible. The figure above gives a best possible result for 4 pegs.
输入
The first line of the input contains a single integer T indicating the number of test cases ( 1<=T<=50). Each test case contains a single integer N ( 1<=N<=50) indicating the number of pegs available.
输出
For each test case, print a line containing an integer indicating the maximum number of balls that can be placed. Print “-1'' if an infinite number of balls can be placed.
样例输入
2
4
25
样例输出
11
337
参考代码
暂无
解析
暂无
