Ok, so in this problem, you will be given N and M, how many ways we can take two numbers from 1 to N so that their absolute difference is divisible by M. As the answer can be quite big, give the modulo of the answer by 1000,000,009.
First line of the input is T(T ≤ 100000), then T test cases follows. Each case have only one line containing two positive integers N and M (1 ≤ N, M ≤ 1018).
For each test case, output a line containing "Case I: d" where I is test case number and d is the answer modulo by 1000000009.
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 (1, 6) and (2, 7).
Note: Based on a true chat.