CSQUARE - Powered and Squared

no tags 

Description

Marko is learning method of successive squaring so that he can calculate a^b mod m quickly. To give himself practice he wrote many tuples of a, b and m and went to school thinking that he will do it after school.

After school he found that tuples he wrote are modified by his little sister. His sister converted each b into base 3. Marko wrote everything in base 10.

Help Marko to do his excercise.

Input

First line of input contains a number T, number of test cases. Then T test cases follows each containing three numbers a (<=10^9), b and m (<=10^5) (a in base 10, b in base 3 and m in base 10). Number of digits in b will be less than 250.

Output

Output a number for each test case a^b mod m in base 10.

Sample

Input:
2
2 10 10
3 21101 19

Output:
8
3

hide comments
numerix: 2010-10-31 05:04:42

Never heard of a little sister doing such silly things ...


Added by:Divyanshu Ranjan
Date:2010-10-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC GAWK MAWK BC C-CLANG NCSHARP CPP14-CLANG CLOJURE COBOL COFFEE D-CLANG D-DMD DART ELIXIR FSHARP FANTOM FORTH GO GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PYTHON3 PY_NBC R RACKET RUST CHICKEN SED SWIFT UNLAMBDA VB.NET