Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Forum Home ProblemSet Status Ranklist Contest LoginRegister Exam
Problem 1085. -- Hanoi Tower Troubles Again!

Hanoi Tower Troubles Again!

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 32  Solved: 21


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.

Sample Input


Sample Output




OIBH Reminiscence Programming Contest



한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin