题目描述
计算 $a \times b \bmod p$，其中 $a,b,p$ 都可以达到 $10^{18}$。要求避免溢出（__int128 或倍增加法）。
输入格式
第一行整数 $T$；接下来 $T$ 行每行三个非负整数 $a, b, p$（$p>0$）。
输出格式
每个询问一行答案。
数据范围
$$1 \le T \le 20,\ 0 \le a,b < p \le 10^{18}$$
计算 $a \times b \bmod p$，其中 $a,b,p$ 都可以达到 $10^{18}$。要求避免溢出（__int128 或倍增加法）。
第一行整数 $T$；接下来 $T$ 行每行三个非负整数 $a, b, p$（$p>0$）。
每个询问一行答案。
1 1 1 2
1
3 2 3 5 123456789 987654321 1000000007 999999999999999998 2 999999999999999999
1 259106859 999999999999999997