Strange Function

All submissions for this problem are available.
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 nonnegative 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 singledigit 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 spaceseparated 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
Example
Input: 3 5 2 7 2 127 1 Output: 7 4 1
Explanation
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
Author:  abx_2109 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/ABX01 
Tags  abx_2109, fastexpo, ltime55, observations, simple 
Date Added:  30102017 
Time Limit:  0.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions