#include <iostream>#include <cmath>#include <cstring>using namespace std;int a[51], sum, T;int p(int w){for(int i = 1; i <= T; i++){int tem_sum = a[i] + w;int gen = (int)sqrt(tem_sum) * (int)sqrt(tem_sum);if(tem_sum == gen || a[i] == 0){a[i] = w;sum++;p(w + 1);return 1;}}return 0;}int main(){int iCase;cin>>iCase;while(iCase--){cin>>T;sum = 0;memset(a, 0, sizeof(a));if(p(1))cout<<sum<<endl;elsecout<<"-1"<<endl;}return 0;}
