Migrated from Lutece 850 方老师开橙卡

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

方老师最近迷上了炉石传说，但是他总是被土豪吊打。

方老师是万能的，他知道如何能开出橙卡：

方老师有一个幸运数字$n$，他开卡包的时候总会在屏幕上划出一个五芒星，假设方老师划出了$m$次五芒星，那么当$(m^2)\%(10^x)=n (x=0,1,2,3\cdots)$，对于某个$x$成立时，就会开出橙卡，请问方老师最少需要划出几次五芒星？如果方老师不可能开出橙卡，请告诉他。

Input

第一行有一个整数$T(T \leq 3000)$，代表测试数据的组数。

对于每组数据，每行有一个整数$N(0 \leq N \leq 10^9)$

Output

对于每一组数据,如果$m$存在，输出$m$，否则输出None

Samples

3
3
21
25

None
11
5

Note

$(m^2)\%(10^x)=n (x=0,1,2,3\cdots)$ 只要有一个$x$满足就成立了

Resources

2014 UESTC Training for Search Algorithm