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
soub5184: 2019-01-30 21:43:28

To the problem setters: please think about java solutions

rahul_107: 2018-11-23 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: 2016-04-15 17:41:44

time limit too strict for java :(

Himanshu Yadav: 2015-11-03 19:12:11

@master_mind you must be converting the the base-3 number into base-10 without using modulo.

Vaporeon: 2015-05-28 22:02:30

"'>>'" does the trick! ;) :D

Archit Jain: 2015-04-01 14:57:03

cin and cout giving tle

NIKHIL KUMAR SINGH: 2014-10-01 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: 2014-03-25 19:10:34

very nice indeed !!

Master_Mind: 2014-03-21 04:54:01

why i am getting wa??????
my program runs well on ideone..


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