Migrated from Lutece 507 搜索乘数

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

任给一个不能被$5$整除的奇数$p$（不超过$4$位），求乘数$s$，使$p\times s$的每一位数字均为$1$。

Input

有多组测试数据。输入的第一行是整数$T$($1\leq T\leq 200$)，表示随后测试数据的组数。每组测试数据占一行，由一个不超过$4$位的整数组成。

Output

对应每组测试数据，输出对应的乘数$s$，使得$p\times s$的每一位数字全为$1$。每组输出占一行。

Samples

1
43

2583979328165374677

Resources

wxiaoping