You are standing at position . One enemy is positioned at for every such that , , and .

You have a single laser beam which you can use to shoot enemies. You can aim it in any direction, and all enemies in that direction will be eliminated. You win if the number of enemies you eliminate is at least and is divisible by .

How many directions can you aim the laser so that you win? As the answer can get very large, output the answer modulo ().

Input Format
The first line contains a single integer, , which is the number of test cases. The next lines each contain three integers separated by single spaces, , and .

Output Format
For each test case, output a single line containing the number of directions you can aim the laser, modulo .

Constraints

Sample Input

2
3 2 1
100 3 2

Sample Output

26
70946

Explanation
For the first test case, here are the 26 directions you can point the laser beam to:
, , , , ,
, , , , ,
, , , , ,
, , , , ,
,