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 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]. (non-negative 32-bit 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: 2015-12-30 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: 2016-09-16 11:17:41
Tarun Dutt: 2015-06-04 16:34:47

Any prerequisites to solve this problem?

aksam: 2015-01-01 10:05:03

@Thomas Dybdahl Ahle why my solution gives NZEC in 4th test case

[Lakshman]: 2014-12-31 16:32:33

@Thomas Dybdahl Ahle can you please check my last submission I am getting WA. Thanks

EDIT:: Finally Accepted.

Last edit: 2015-01-02 18:37:17
(Tjandra Satria Gunawan)(曾毅昆): 2014-08-25 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: 2014-05-03 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...
--(edit,Francky)--> I answer myself. NZEC was caused by an import of a function available starting Py3.3. Now I have AC in Py3.2 too.

Last edit: 2014-05-04 03:46:03
Alessandro Amici: 2014-03-30 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: 2012-05-02 13:06:16

pulkit: You have errors in some towers of 0, and large towers of 2.
Xusha: You have errors in your formating and in most big towers.

Thomas Dybdahl Ahle: 2012-04-14 04:25:59

I have disqualified the solutions by hqztrue and zzy since they were identical to the solution submitted by DHH.

suhang: 2012-04-10 03:01:43

@Thomas Dybdahl Ahle
Can you give me some test i'm getting WA?
T_T


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