题目描述

不编题面了。请计算

其中 $p$ 质数。

输入格式

第一行有一个数字 $T(T \leqslant 10^5)$，表示数据组数。

接下来 $T$ 行每行有三个数字，分别为 $a,b,p$，其中 $1 \leqslant a, b, p \leqslant 10^9$。

输出格式

共 $T$ 行，每行有一个数字，表示答案。

样例

1
2 3 7

5