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 associative. 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 height 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 integers).
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
suhang:
20120410 03:01:43
@Thomas Dybdahl Ahle


pulkit:
20120409 19:34:06
@Thomas: My code seems to work correctly.. Can't really find any corner case...


Anirvan Sarkar:
20120207 11:36:05
@Thomas Dybdahl Ahle:


Thomas Dybdahl Ahle:
20120204 00:30:50
@Anirvan Sarkar: You fail "2 20"


Santiago Palacio:
20120204 00:19:52
Yes, i know you can deduce it from that, but what i say is that with problems like this, it's not always that obvious and should be more explicit. 

Mitch Schwartz:
20120204 00:19:52
@Santiago: 2^2^2^2 = 2^2^4 = 2^16 = 65536 is unambiguous. You can notice that ((2^2)^2)^2 would make 256. 

Anirvan Sarkar:
20120204 00:19:52
@Thomas Dybdahl Ahle


Santiago Palacio:
20120204 00:19:52
It's 2^(2^(2^2))) right? (I think the problem statement is not fully clear about it, as it could be (((2^2)^2)^2). 

Thomas Dybdahl Ahle:
20120204 00:19:52
@numerix: np. But I'm wondering if the bug shows that your method isn't strong enough for general mods? 

Thomas Dybdahl Ahle:
20120204 00:19:52
Hi numerix, you are right. Test data was wrong for 0(2n). It's fixed now. Thank you.

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