Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Numbers Tell

By ridowan007 · Limits 2s, 1.0 GB


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.

Input

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).

Output

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.

Sample

InputOutput
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.

Discussion

Statistics


45% Solution Ratio

Double_OEarliest, Apr '18

raiyan.sidneFastest, 0.0s

Double_OLightest, 2.2 MB

raiyan.sidneShortest, 301B

Submit

Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.