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
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..

Ouditchya Sinha: 2013-03-18 06:29:25

Nice problem... Learnt something new today. :)

Hamdi Ahmadi Muzakkiy: 2013-01-24 07:45:59

give me some testcase -.-

Bharath Reddy: 2012-08-08 13:48:34

cin and cout gave TLE.
scanf and printf AC

Allada Revanth Kumar: 2012-01-30 04:27:05

yes what numerix said is right.... time limit should be increased

Aamir Khan: 2011-10-26 17:06:35

What is the best way to convert a number from base 3 to base 2 ?

EHACKER: 2011-09-19 04:32:23

TLE


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