use std::collections::BTreeMap;

use proconio::input;

const MAX: usize = 10_usize.pow(9);

fn main() {
    input! {
        t: usize,
        nn: [usize; t],
    }

    let mut square_numbers_per_num_zeros = vec![BTreeMap::new(); 10];

    for i in 0_usize.. {
        let i2 = i.pow(2);

        if i2 > MAX {
            break;
        }

        let (num_zeros, sorted_chars) = parse(i2);
        let square_numbers = &mut square_numbers_per_num_zeros[num_zeros];
        if !square_numbers.contains_key(&sorted_chars) {
            square_numbers.insert(sorted_chars, i2);
        }
    }

    for &n in &nn {
        let (num_zeros, sorted_chars) = parse(n);
        let square_number = square_numbers_per_num_zeros[..=num_zeros]
            .iter()
            .filter_map(|square_numbers| square_numbers.get(&sorted_chars))
            .min();
        match square_number {
            Some(value) => println!("{}", value),
            None => println!("-1"),
        }
    }
}

fn parse(n: usize) -> (usize, String) {
    let mut chars: Vec<_> = n.to_string().chars().collect();
    chars.sort_unstable();
    let num_zeros = chars.iter().take_while(|&&ch| ch == '0').count();
    (num_zeros, chars[num_zeros..].iter().collect())
}