4510 - Mod

• Submit
• Status
• Discuss
• Summary

Description

1에 A를 n번 곱한 값을 B로 나눈 나머지를 구해보자.

Input

Line 1: 입력 갯수 N (1≤N≤10000)

Line 2~N+1: A, n, B가 공백으로 구분되어 입력된다. (1 ≤ A,n,B ≤ 1000)

Output

* Line 1~N : A를 n번 곱한 값을 B로 나눈 나머지를 출력한다.

Sample Input

2
2 3 5
541 844 547

Sample Output

3
540

Hint

Overflow를 조심하세요!

 

10%7=3

100%7=30%7=2

1000%7=20%7=6

10000%7=60%7=4

100000%7=40%7=5

1000000%7=50%7=1

10000000%7=10%7=3