GuGuFishtion

Problem Description

Input

Input contains an integer $T$ indicating the number of cases, followed by $T$ lines. Each line contains three integers $m$,$n$,$p$ as described above. $1\le T\le 3$ $1\le m,n\le 1,000,000$ $\max(m,n)<p\le 1,000,000,007$ And given $p$ is a prime.

Output

Please output exactly $T$ lines and each line contains only one integer representing the answer.

Sample Input

1

5 7 23

Sample Output

2

Source

2018 Multi-University Training Contest 7