You will be given and , how many ways we can take two numbers from 1 to so that their absolute difference is divisible by . As the answer can be quite big, give the modulo of the answer by ().
First line of the input is (), then test cases follows. Each case have only one line containing two positive integers and ().
For each test case, output a line containing "Case I: d" where is test case number and is the answer modulo by .
Input | Output |
---|---|
2 4 3 7 5 | Case 1: 1 Case 2: 2 |
In the first case, There we can only take 1 and 4 between 1 to 4 whose difference 3 is divisible by 3. For second case the pairs are and . |