请注意此题特殊的时间限制。

题目背景

小 A 非常喜欢 $a^b$，因此也喜欢快速幂。

题目描述

现在小 A 想求出 $a^b \bmod 10$ 的值，但是小 $A$ 怕你使用随机数随机出正确答案，因此会问你 $q$ 次。

输入格式

第一行输入一个正整数 $q$，

之后 $q$ 行每行输入两个正整数 $a,b$。

输出格式

对于每组询问，你需要给出一个数表示 $a^b \bmod 10$ 的值。

输入输出样例 #1

输入 #1

2
2 6
4 2

输出 #1

4
6

说明/提示

【样例解释 #1】

$2^6 \bmod 10 = 4,4^2 \bmod 10=6$。

【样例 #2】

见下发文件。

该样例满足测试点 $11 \sim 12$ 的限制。

【样例 #3】

见下发文件。

该样例满足测试点 $19 \sim 20$ 的限制。

【数据范围】

对于所有数据，$1 \le q \le 10^5$，$0 \le a \le 10$，$1 \le b \le 10^{100}$。

其中：

• 特殊性质 A：保证 $a=8$；

• 特殊性质 B：保证 $b=10^{100}-797$。