#include <bits/stdc++.h>
#define NUM 10005
using namespace std;
int dp[NUM];
int n, num;

int main()
{
    for(int i = 1; i <= 4; ++i) dp[i] = i;

    for (int i = 4; i < NUM; i++)
    {
        dp[i] = i;

        for (int x = 1; x <= ceil(sqrt(i)); x++)
        {
            int aux = x * x;
            if (aux > i)
                break;
            else
                dp[i] = min(dp[i], 1 + dp[i - aux]);
        }
    }

    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        cin >> num;
        cout << dp[num] << '\n';
    }
    return 0;
}