题解 | 快速乘

import sys


"""

 a*b mode p 

 b转为二进制
 快速乘法（a*b mod p）是一种用于计算大整数乘法取模的高效算法，特别适用于a和b规模较大（如达到10^18级别）时避免溢出的场景。其核心思想是将乘法转换为二进制分解的加法运算，结合模运算性质降低计算复杂度‌ 

"""
# for line in sys.stdin:
#     a = line.split()
#     print(int(a[0]) + int(a[1]))
def  sovler():
    def  fun(a,b,p):
        res=0
        while b>0:
            if b%2==1:
                res =(res+a)%p
            a=a*2
            b=b//2
        return res
    n =int(input())
    for i in range(n):
        line =input()
        lines=line.split(" ")
        a= int(lines[0])
        b= int(lines[1])
        p =int(lines[2])
        ret=fun(a,b,p)
        print(ret)
sovler()