T144501 「Beta2020」整除

给定正整数 $n$，试构造出一个最小的正整数 $k$，使得对于任意能被 $n$ 整除的正整数 $a$，$a$ 的后 $k$ 位和前面部分的差也能被 $n$ 整除。

**本题有多组测试数据。** 第一行，一个整数 $T$，表示数据组数。 对于每组数据： 一行，一个整数 $n$。

对于每组数据，输出一行，若 $k$ 有解，输出 $k$ 的最小正整数解；否则，输出 $-1$。

| Subtask | $n$ | 分值 | | :------: | :------: | :------: | | $1$ | $1 \leq n \leq 10^5$ | $30 \operatorname{pts}$ | | $2$ | 无特殊限制 | $70 \operatorname{pts}$ | 对于 $100\%$ 的数据，$1 \leq n \leq 10^9$，$1 \leq T \leq 100$。