Vấn đề MODULO


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 10M

Author:
Problem type

Cho số nguyên dương a, b, M, trong đó a là số rất lớn được biểu diễn như một xâu ký tự số.

Hãy tìm K = (ab ) %M. Ví dụ a = 3, b=2, M = 4 thì K = (32)%4 = 1

Input

Dòng đầu tiên đưa vào số lượng test T.

Những dòng kế tiếp mỗi dòng đưa vào một test. Mỗi test là bộ ba a, b, M được viết trên một dòng.

T, a, b, M thỏa mãn ràng buộc : 1≤T≤100; 0≤length(a) ≤1000; 2≤ b, M ≤1012 .

Output

Đưa ra kết quả mỗi test theo từng dòng.

Example

Input
2
2 3 5
3 2 4

Output
3
1

utc

Comments


  • 1
    haidv  commented on April 11, 2020, 12:46 p.m.

    bài này bị sai test a ơi


  • 1
    Nam_CNTT2_K58  commented on April 11, 2020, 12:07 p.m.

    ad sửa test cho python chạy đc cái.