#include<bits/stdc++.h>
using namespace std;
const long long M=2e5+1,MOD=1000000007;
typedef long long ll;
int dp[M];
void precalculate(){
    dp[0]=1;
    for(int i=1;i<M;i++)dp[i]=MOD;
    for(int i=1;i*i<=2e5;i++){
        vector<int>temp(M,MOD);
        int l=i*i;
        for(int j=l;j<M;j++){
            
             if(dp[j-l]!=MOD && dp[j-l]){
                temp[j]=min(temp[j],dp[j-l]+1);
             }
             temp[j]=min(dp[j],temp[j]);
        }
        for(int j=l;j<M;j++)dp[j]=min(dp[j],temp[j]);
    }
 for(int i=1;i<=2e5;i++)if(dp[i]==MOD)dp[i]=0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    precalculate();
    cin>>t;
    while(t--){
    int x;
    cin>>x;
    cout<<dp[x]-1<<"\n";

    
      
     
    }




    
   
   return 0;
 
}