POWTOW  Power Tower City
You are living in a city build entirely of power towers such as 3^3^3 and 10^10^10^10. To enter a building you must type the last 9 digits of the number represented by the tower, written in decimal form, on a keypad next to the main entrance. You are not sharp enough at mental maths, but you can write a handy program to bring along in your pocket.
A power tower is defined as repeated exponentiation. We write this using Knuth's uparrow notation as: e↑↑a = e^e^...^e (a terms). Remember that ^ (exponentiation) is right assosiative. For example: 2↑↑4 = 2^2^2^2 = 2^(2^(2^2)) = 2^2^4 = 2^16 = 65536, and 3↑↑1 = 3. The value of a tower of heigh 0 is 1.
Input
The first line contains integer C in [0..1000], the number of test cases.
Then follows C lines, each with integers e,a in [0..2147483647]. (nonnegative 32bit ints).
Output
For each testcase output e↑↑a, or if the output has more than 9 digits, output "..." and then the last 9 digits.
Example
Input:
3
0 0
2 5
993306745 75707320 Output:
1
...719156736
...884765625
hide comments
Thomas Dybdahl Ahle:
20151230 20:04:36
@Tarun There are multiple ways to solve it, but I don't think I spoil anything if I say it'll help to know a bit of modular arithmetic, and maybe Euler's theorem. Last edit: 20160916 11:17:41 

Tarun Dutt:
20150604 16:34:47
Any prerequisites to solve this problem? 

aksam:
20150101 10:05:03
@Thomas Dybdahl Ahle why my solution gives NZEC in 4th test case 

[Lakshman]:
20141231 16:32:33
@Thomas Dybdahl Ahle can you please check my last submission I am getting WA. Thanks


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20140825 05:51:41
There are many crazy corner case in this problem, and it's fun to discover them all :D Very nice problem :) 

Francky:
20140503 01:33:14
@psetter : I've made intense check and I'm unable to get NZEC (at home) with my Python code, could you give me a reason for NZEC here ; I tried several input methods...


Alessandro Amici:
20140330 10:06:20
Ok, I did all sort of dumb mistakes, but now I can't see which corner cases I'm still missing in ID 11354832 :/ Any hint? 

Thomas Dybdahl Ahle:
20120502 13:06:16
pulkit: You have errors in some towers of 0, and large towers of 2.


Thomas Dybdahl Ahle:
20120414 04:25:59
I have disqualified the solutions by hqztrue and zzy since they were identical to the solution submitted by DHH. 

suhang:
20120410 03:01:43
@Thomas Dybdahl Ahle

Added by:  Thomas Dybdahl Ahle 
Date:  20111121 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 