小明是一个十分喜爱数学的孩子，在一节数学课上，他把2的n次方 (n＞0) 写在一张纸上，然后惊奇的发现：2,4,8,16,32,64,128……这组数的个位始终按照“2,4,8,6,2,4,8,6……”的规律进行微循环。小明猜想，既然个位数能循环，那么后五位数也应该会存在循环，请帮小明验证这个猜想。
输入描述:
第一行，一个整数T (1≤T≤100000)，表示案例的个数
接下来的T行，每行一个整数x(0≤x＜100000)，来代表小明想要验证的最后五位数，我们应为不足五位数的案例补上前导0
输出描述:
T行，T个整数
每行输出对应案例的结果：如果案例出现在了2的n次方(n＞0)的尾数中，请输出第一次出现的指数，，如果案例不会出现在所有尾数中，请输出0
示例2
说明
分析示例1，对于四组案例，只有第二组(00002)可能出现，即2的1次方等于2，因此输出1，而对于其他案例，无论2的多少次方末尾五位数都是不会出现00010的。