[http://online-judge.uva.es/p/v102/10276.html 원문보기]
----
인기도:B(A,B,C), 성공률:높음(낮음,보통,높음), 레벨:3(1~4)

=== About [HanoiTowerTroublesAgain!] ===
하노이의 탑 문제를 변형시킨 문제들 중에도 흥미로운 문제들이 많이 있다. 이 문제는 N개의 기둥과 1부터 무한대까지의 정수가 적혀있는 공에 관한 문제다. 두 공에 적힌 번호의 합이 완전제곱수(어떤 정수를 제곱한 수)가 아니면 그 두 공 사이에는 서로 맞닿아있을 수 없을 만큼 큰 척력이 작용하게 된다.
[http://online-judge.uva.es/p/v102/p10276.jpg]
공을 한 번에 하나씩, 번호가 커지는 순서로 기둥에 끼우는 게임을 한다(즉 1번을 끼우고 나서 2번을 끼우고, 그리고 나서 3번을 끼우고 하는 식으로 공을 기둥에 끼움). 더 이상 서로 밀어내지 않도록 공을 끼울 수 없게 되면 게임이 끝난다. 게임의 목표는 최대한 많은 개수의 공을 끼우는 것이다. 위에 있는 그림에는 기둥이 네 개인 경우에 최대한 많은 공을 끼운 결과가 나와 있다.

=== Input ===
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 T(1≤T≤50)가 입력된다. 각 테스트 케이스마다 쓸 수 있는 기둥의 개수를 나타내는 정수 N(1≤N≤50)이 입력된다.

=== Output ===
각 테스트 케이스에 대해 기둥에 끼울 수 있는 공의 최대 개수를 나타내는 정수를 출력한다. 끼울수 있는 공의 개수가 무한대면 '-1'을 출력한다.

=== Sample Input ===
{{| 2
4
25 |}}

=== Sample Output ===
{{| 11
337 |}}

=== 풀이 ===
 || 작성자 || 사용언어 || 개발시간 || 코드 ||
 || 문보창 || C++ || 10분 || [HanoiTowerTroublesAgain!/문보창] ||
 || 황재선 || Java || 50분 || [HanoiTowerTroublesAgain!/황재선] ||
 || 하기웅 || C++ || 원랜 1시간, 문보창 XXX 때문에 말렸음ㅡㅡ; || [HanoiTowerTroublesAgain!/하기웅] ||
 || 이도현 || C++ || Closed Form 구하는 데(1시간 30분), 코딩 5분 || [HanoiTowerTroublesAgain!/이도현] ||
 || [조현태] || C++ || ? || [HanoiTowerTroublesAgain!/조현태] ||

=== 쓰레드 ===
----
[문제분류] [경시대회준비반]