题解 | #快速乘#

import sys

lines = []
for line in sys.stdin:
    a = line.split()
    lines.append(a)

for i in range(int(lines[0][0])):
    cur_line = lines[i+1]
    
    aa = int(cur_line[0])
    bb = int(cur_line[1])
    pp = int(cur_line[2])

    add_result = 0

    while 1:
        if bb == 0:
            add_result = 0
            break
        if bb == 1:
            add_result += aa
            break
        else:
            if bb % 2 == 1:
                add_result += aa  # 除2余1，意味着在此二进制位为1，则执行一次+=
            aa = (aa + aa)  # 每执行一步，相当于aa乘以2^n
            bb = bb // 2

    result = add_result % pp
    print(result)