U426644 【模板】快速乘

给出正整数 $a,b,p$ 求出 $a\times b$ 对 $p$ 取余的余数。 没个测试点共 $T$ 组数据。

第一行为一个正整数 $T$，表示测试数据组数。 接下来 $T$ 行，每行三个正整数 $a,b,p$。

对于每行数据，输出一行一个正整数表示 $a\times b$ 对 $p$ 取余的余数。

本题采用捆绑测试。 对于测试点 $1$，保证 $a,b,p\le3000$，占 $20$ 分。 对于测试点 $2$，保证 $a,b,p\le10^9$，占 $30$ 分。 对于测试点 $3$，无任何限制，占 $50$ 分。 对于所有数据，保证 $1\le T\le10^5$，$1\le a,b,p\le 10^{18}$