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 up-arrow 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]. (non-negative 32-bit 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

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

hide comments
2012-02-04 00:19:52 numerix
@Thomas: Thanks for the hint (stupid mistake!).

Last edit: 2011-11-25 20:50:24
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.