From: 2020-03-16 00:00:00 To: 2020-07-01 00:00:00 Now: 2024-11-15 16:54:17 Status: Public

N - Mod

Time Limit: 1s Memory Limit: 128MB

Submissions: 398 Solved: 124

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