PWRANDMOD - Power and Mod

## 题目描述 给出三个数 $a$、$b$、$m$，计算 $a^b \bmod m$的值 ## 输入格式 第一行为整数 $n$，表示有 $n$ 组数据； 下面 $2\sim n+1$ 行，每行输入 $a$、$b$、$m$ 的值。 ## 输出格式 一共 $n$ 行，每行输出 $a^b \bmod m$ 。 感谢@Steve_bm 提供的翻译

Exponentiation is a mathematical operation, written as _b $ ^{n} $_ , involving two numbers, the base _b_ and the exponent _n_. When _n_ is a positive integer, exponentiation corresponds to repeated multiplication of the base: that is, _b $ ^{n} $_ is the product of multiplying _n_ bases: _b $ ^{n} $_ = b x b x b x .......... x b In computing, the modulo operation finds the remainder after division of one number by another (sometimes called _modulus_). Given two positive numbers, _a_ (the dividend) and _n_ (the divisor), _a_ modulo _n_ (abbreviated as _a_ mod _n_) is the remainder of the Euclidean division of _a_ by _n_. For instance, the expression "5 mod 2" would evaluate to 1 because 5 divided by 2 leaves a quotient of 2 and a remainder of 1, while "9 mod 3" would evaluate to 0 because the division of 9 by 3 has a quotient of 3 and leaves a remainder of 0; there is nothing to subtract from 9 after multiplying 3 times 3. Now, you are given the value of a,b and m. print the value of **a $ ^{b} $ mod m**

First line contains the number of test cases t (1 <= t <= 10 $ ^{4} $ ). Next t line contains three integers a, b and m. where 1 <= a, b <= 10 $ ^{9} $ and 1 <= m <= 2 $ ^{64} $

For each test case print the answer of the problem. #### Sample input ``` 2 2 3 4 3 4 5 ``` #### Sample output ``` 0 1 ```