I-新快速幂

题目描述

Problem Description

快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。 这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。

小明今天学会了快速幂，他感觉自己要起飞了！芜湖~~~

但这时小明暗恋已久的小红却给他出了一道难题： 给定一个整数n，小红不想知道nn等于多少，而想知道nn最高位数字是几，(符号^表示次方) "哈哈，这不是快速幂水题吗，魔改一下就行了！"小明一边说一边码起了代码。

眼看着小明已经上机开码，面对你同样心仪的小红，你愿意甘拜下风？

Input

第一行给定T，表示有T组数据， 每组数据给定题目中的n，(1