def main():
    M = 200001
    MOD = 1000000007
    dp = [MOD] * M
    dp[0] = 1  # Base case

    for i in range(1, M):
        l = i * i
        if l >= M:
            break

        temp = [MOD] * M
        for j in range(l, M):
            if dp[j - l] != MOD and dp[j - l] > 0:
                temp[j] = min(temp[j], dp[j - l] + 1)
            temp[j] = min(dp[j], temp[j])

        for j in range(l, M):
            dp[j] = min(dp[j], temp[j])

    for i in range(1, M):
        if dp[i] == MOD:
            dp[i] = 0  # Mark as unreachable
    t = int(input())
    for _ in range(t):
        x = int(input())
        print(dp[x] - 1)  # Output the result

if __name__ == "__main__":
    main()