# Generated By Gemini 2.5 Pro

import sys

def solve():
    """
    1つのテストケースを解決する関数
    """
    # 標準入力からNを文字列として読み込む
    n_str = sys.stdin.readline().strip()
    if not n_str:
        return

    n_len = len(n_str)
    # Nの各桁の数字をソートして、比較の基準とする
    n_chars_sorted = sorted(n_str)

    # 探索する平方数の上限を計算する
    # i*i が N と同じ桁数以下である範囲で探す
    # i*i < 10**n_len  =>  i < sqrt(10**n_len)
    limit = int((10**n_len)**0.5)

    # i=0から順に探索し、最初に見つかったものが最小の平方数となる
    for i in range(limit + 1):
        square = i * i
        
        # 平方数をNと同じ桁数になるよう左側を'0'で埋める
        padded_square_str = str(square).zfill(n_len)

        # 桁の構成が同じかどうかをソートして比較する
        if sorted(padded_square_str) == n_chars_sorted:
            print(square)
            return

    # ループを抜けても見つからなかった場合
    print(-1)


def main():
    """
    メイン処理
    T個のテストケースを処理する
    """
    try:
        # テストケースの数を読み込む
        t_str = sys.stdin.readline()
        if not t_str:
            return
        T = int(t_str)
        
        # 各テストケースについてsolve()を呼び出す
        for _ in range(T):
            solve()
    except (IOError, ValueError):
        # 入力エラー処理
        return

if __name__ == "__main__":
    main()