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

### Statistics

45% Solution Ratio

Double_OEarliest, Apr '18

raiyan.sidneFastest, 0.0s

Double_OLightest, 2.2 MB

raiyan.sidneShortest, 301B

### Submit 