const M: usize = 200_001; // Adjusted to Rust syntax
const MOD: i64 = 1_000_000_007;

fn precalculate() -> Vec<i64> {
    let mut dp = vec![MOD; M]; // Initialize the dp array
    dp[0] = 1; // Base case

    for i in 1.. {
        let l = i * i;
        if l >= M {
            break; // Stop if square exceeds limit
        }

        let mut temp = vec![MOD; M]; // Temporary dp array
        for j in l..M {
            if dp[j - l] != MOD && dp[j - l] > 0 {
                temp[j] = temp[j].min(dp[j - l] + 1);
            }
            temp[j] = temp[j].min(dp[j]);
        }
        for j in l..M {
            dp[j] = dp[j].min(temp[j]);
        }
    }

    for i in 1..M {
        if dp[i] == MOD {
            dp[i] = 0; // Mark as unreachable
        }
    }

    dp
}

fn main() {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();
    let t: usize = input.trim().parse().unwrap();

    let dp = precalculate(); // Precalculate dp values

    for _ in 0..t {
        let x: usize = {
            input.clear();
            std::io::stdin().read_line(&mut input).unwrap();
            input.trim().parse().unwrap()
        };
        println!("{}", dp[x] - 1); // Output the result
    }
}