Numbers Tell

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 $1000000009$ ($1e9+9$).

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 ≤ 10^{18}$).

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

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 $(1, 6)$ and $(2, 7)$.