# Generated By Gemini 2.5 Pro

import sys

# --- 事前計算 ---
# プログラム開始時に一度だけ実行する
# maps_by_len[d] は、d桁の数に対する {桁の構成: 最小の平方数} を格納する辞書
maps_by_len = [{} for _ in range(11)] 

# Nは最大10^9 (10桁)。並び替えた数も10桁以下になる。
# 10桁以下の最大の平方数は (10^10-1) なので、その平方根までループすれば十分。
limit = int((10**10)**0.5)

for i in range(limit + 1):
    square = i * i
    s_str = str(square)
    len_s = len(s_str)
    
    # この平方数sが、d桁の数Nの並び替えで作れる場合を考える (d >= len_s)
    # 不足分は先頭の'0'で補う
    for d in range(len_s, 11):
        # d桁になるように左側を'0'で埋める
        padded_str = s_str.zfill(d)
        # 桁の構成をタプル（辞書のキーとして使える）にする
        signature = tuple(sorted(padded_str))
        
        # この構成がまだ辞書になければ、現在の平方数を追加する
        # iが小さい順なので、最初に追加されたものが最小の平方数となる
        if signature not in maps_by_len[d]:
            maps_by_len[d][signature] = square

# --- メイン処理 ---
def solve():
    """
    1つのテストケースを解決する関数
    事前計算された結果をO(1)で検索する
    """
    n_str = sys.stdin.readline().strip()
    if not n_str:
        return
        
    n_len = len(n_str)
    n_signature = tuple(sorted(n_str))
    
    # 対応する桁数の辞書から、Nの桁構成に一致する答えを取得する
    # 存在しない場合は -1 を返す (dict.getのデフォルト値)
    result = maps_by_len[n_len].get(n_signature, -1)
    print(result)


def main():
    """
    T個のテストケースを処理する
    """
    try:
        t_str = sys.stdin.readline()
        if not t_str:
            return
        T = int(t_str)
        
        for _ in range(T):
            solve()
            
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()