~java
import static java.lang.Math.ceil;
import static java.lang.Math.floor;
import static java.lang.Math.sqrt;

import java.util.Scanner;

public class HanoiTower {
	
	public int readNumber() {
		return new Scanner(System.in).nextInt();
	}
	
	public boolean canBallPut(int[] prev, int peg, int ballNumber) {
		if (prev[peg] == 0) {
			return true;
		}
		double squareNumber = sqrt(prev[peg] + ballNumber);
		return ceil(squareNumber) == floor(squareNumber);
	}
	
	public int maxBall(int numOfPeg) {
		int[] prevNumber = new int[numOfPeg + 1];
		
		int ballNumber = 1;
		int oldBallNumber = 0;
		while(oldBallNumber != ballNumber) {
			oldBallNumber = ballNumber;
			for(int peg = 1; peg <= numOfPeg; peg++) {
				if (canBallPut(prevNumber, peg, ballNumber)) {
					prevNumber[peg] = ballNumber++;
					break;
				}
			}
			if (ballNumber == Integer.MAX_VALUE) {
				return -1;
			}
		}
		return ballNumber - 1;
	}
	
	public void printNumberOfBall(int numOfBall) {
		System.out.println(numOfBall);
	}

	public static void main(String[] args) {
		HanoiTower hanoi = new HanoiTower();
		
		int testCase = hanoi.readNumber();
		for(int i = 0; i < testCase; i++) {
			int numOfPeg = hanoi.readNumber();
			int numOfBall = hanoi.maxBall(numOfPeg);
			hanoi.printNumberOfBall(numOfBall);
		}
	}
}