Read problems statements in Mandarin chinese, Russian and Vietnamese as well.

As New Year is approaching, Salik is studying functions in order to sharpen his math skills. Instead of regular functions, he is studying a strange function F which operates on non-negative integers. The value of F(A) is obtained by the following process:

Compute the sum of digits of A; let's denote this sum by S.
If S is a single-digit integer, then F(A) = S.
Otherwise, F(A) = F(S).

It's guaranteed that this process correctly defines the function F.

Since this problem was pretty straightforward, he invented a new problem: Given two integers A and N, compute F(A^{N}). Can you help him solve this task?

------ Input ------

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains two space-separated integers A and N.

------ Output ------

For each test case, print a single line containing one integer — the value of F(A^{N}).

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ A, N ≤ 10^{18}$

------ Subtasks ------

Subtask #1 (10 points):

$1 ≤ N ≤ 3$
$1 ≤ A ≤ 10^{5}$

Subtask #2 (20 points):

$1 ≤ N ≤ 100$
$1 ≤ A ≤ 10^{5}$

Subtask #3 (70 points): original constraints

----- Sample Input 1 ------
3
5 2
7 2
127 1
----- Sample Output 1 ------
7
4
1
----- explanation 1 ------
Example case 1: F(5 · 5) = F(25) = F(2+5) = F(7) = 7 Example case 2: F(7 · 7) = F(49) = F(4+9) = F(13) = F(1+3) = F(4) = 4
Example case 3: F(127) = F(1+2+7) = F(10) = F(1+0) = F(1) = 1

见题面

见题面