5235：Door game

CodeFamer is developing a game which is called Door Game(DG). In this game, player is expected to open some doors to win the game. There is a problem on each door, if player can give correct answer to the problem then the door will open. In a certain door, there are two integers n and k. There are some words on the door, it says:

$F\left( n \right) = \left\{ \begin{array}{l}
n{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} if{\kern 1pt} {\kern 1pt} {\kern 1pt} n < = 1\\
F\left( {n - 1} \right) + F\left( {n - 2} \right){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} otherwise
\end{array} \right.,S\left( n \right) = \sum\limits_{i = 0}^n {DS(F(i)\% F(k))} $ .

DS(x) means the digit sum of x. For example DS(0)=0,DS(1)=1,DS(10254)=1+0+2+5+4=12. If you can calculate S(n), the door will open, then you can advance to the next door.

In order to check play’s answer, CodeFamer should write a program to generate the right answer. However he is busy in designing the UI, so he wants you to help him to write the program.

Here is your task, when given certain n and k, you should calculate S(n).

There are multiple test cases. In the first line of the input file there is an integer T indicates the number of test cases.

In the next T lines, each line contains n and k which were mentioned above.

[Technical Specification]

All input items are integers.

1<= T <= 60000

0<=n<=100000000000000 (1e14)

1 <= K <= 1000

For each case，the output should occupies exactly one line. The output format is Case #id: ans, here id is the data number starting from 1; ans is the result you are expected to output.

See the sample for more details.