CSQUARE  Powered and Squared
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
soub5184:
20190130 21:43:28
To the problem setters: please think about java solutions 

rahul_107:
20181123 18:16:18
don't know why tile limit is strict for java.....submitted successfully with the same logic in c++...help me how can I reduce TLE in java any resources to study? 

minhthai:
20160415 17:41:44
time limit too strict for java :( 

Himanshu Yadav:
20151103 19:12:11
@master_mind you must be converting the the base3 number into base10 without using modulo. 

Vaporeon:
20150528 22:02:30
"'>>'" does the trick! ;) :D 

Archit Jain:
20150401 14:57:03
cin and cout giving tle 

NIKHIL KUMAR SINGH:
20141001 05:16:20
Don't know why I am gettting TLE in C ......Using fmod and Modulus Exponentiation in the program ......Please HELP!!


Rishav Goyal:
20140325 19:10:34
very nice indeed !! 

Master_Mind:
20140321 04:54:01
why i am getting wa??????

Added by:  Divyanshu Ranjan 
Date:  20101026 
Time limit:  0.316s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM32GCC GAWK MAWK BC CCLANG CPP14CLANG CLOJURE COBOL COFFEE DCLANG DDMD DART ELIXIR FSHARP FANTOM FORTH GO GOSU GRV JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PYTHON3 PY_NBC R RACKET RUST CHICKEN SED SWIFT UNLAMBDA VB.NET 