Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss 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: 4  Solved: 2
[Submit][Status][Discuss]

Description

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.

Input

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.

Output

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

2
4
25

Sample Output

11
337

HINT

Source

OIBH Reminiscence Programming Contest

[Submit][Status][Discuss]

HOME Back

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