use std::collections::BTreeMap;

use proconio::input;

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

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

    let square_numbers = (0_usize..)
        .take_while(|i| i.pow(2) <= MAX)
        .map(|i| {
            let value = i.pow(2);
            (to_sorted_chars(value), value)
        })
        .collect::<Vec<_>>();
    let square_numbers: BTreeMap<_, _> = square_numbers.into_iter().rev().collect();

    for &n in &nn {
        let sorted_chars = to_sorted_chars(n);
        let square_number = square_numbers.get(&sorted_chars);
        match square_number {
            Some(value) => println!("{}", value),
            None => println!("-1"),
        }
    }
}

fn to_sorted_chars(n: usize) -> String {
    let mut chars = n
        .to_string()
        .chars()
        .filter(|&ch| ch != '0')
        .collect::<Vec<_>>();
    chars.sort_unstable();
    chars.iter().collect()
}