Limits
1s, 512 MB
How many arrays of length N are there such that all elements in the array is in range 1 to M(inclusive) and the LCM of the elements of the array is divisible by D ? As the result can be large, output it modulo 998244353 .
Input
The first line contains T(1<=T<=10). Each testcases contain three integers N , M , D ( 1<= N , M , D <= 107 ).
Output
For each case, at first print the case number then the number of arrays modulo 998244353 . For details, please follow the sample input-output format.
Sample
| Input | Output |
|---|---|
3 2 5 1 1 10 2 2 10 4 | Case 1: 25 Case 2: 5 Case 3: 36 |
LCM stands for Lowest Common Multiple.
