/*
 *   Copyright (c) 2024 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using minheap = priority_queue<long long, vector<long long>, greater<long long>>;
typedef tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key

#define ll int
#define life_is_a_race ios::sync_with_stdio(false); cin.tie(nullptr);


vector<ll> dp(200005,1000),crnt(200005);
vector<ll>v;


int main()
{
    life_is_a_race
    v.push_back(0);
    for(int i=1;i*i<=100000;i++) v.push_back(i*i);
    int m = v.size();
    dp[0] = 0;
    for(int i=1;i<m;i++)
    {
        for(int j=0;j<=100000;j++)
        {
            if(j==0) crnt[j] = 0;
            else if(j>=v[i]) crnt[j] = min(dp[j] , dp[j-v[i]] + 1);
            else crnt[j] = dp[j];
        }
        dp = crnt;
    }
    // for(int i=0;i<=1000;i++)
    // {
    //     cout<<dp[i]<<" "; cout<<endl;
    // }

    int t,x,ans; cin>>t;
    while(t--)
    {
        cin >> x;
        ans = dp[x];
        if(ans>=1000) cout<<-1<<'\n';
        else cout<<ans<<'\n';
    }
}