题解 | #快速乘#

import sys

q = int(input())
# 1.（a+b）%p=(a%p+b%p)%p 
# 2. (a-b)%p=(a%p-b%p)%p  
# 3. (a*b)%p=(a%p*b%p)%p
# 一般 (a*b)%p = ((a+a)%p + b//2 %p)%p, 注意b是否能整除
for i in range(q):
    a,b,p = list(map(int,input().split(' ')))
    res = 0
    base = 1
    while b:
        if b%(base+base)!=0:
            res = (res+a) % p
            b -= base
        a = (a+a)%p
        base = base + base
    print(res)