~cpp
// 10276 - HanoiTowerTroublesAgain!
#include <iostream>
using namespace std;
#include <cmath>
#define MAX_SIZE 50
static int stick[MAX_SIZE+1];
void initStick(int n)
{
for (int i = 1; i <= n; i++) stick[i] = 0;
}
bool isSqure(double n)
{
double k = sqrt(n);
return (k == floor(k)) ? true : false;
}
void process(int n)
{
initStick(n);
bool isGo = true;
int number = 1;
while (isGo)
{
isGo = false;
for (int i = 1; i <= n; i++)
{
if (stick[i] == 0 || isSqure(stick[i] + number))
{
stick[i] = number++;
isGo = true;
break;
}
}
}
cout << number - 1 << endl;
}
int main()
{
int nCase, n;
cin >> nCase;
for (int i = 0; i < nCase; i++)
{
cin >> n;
process(n);
}
return 0;
}