问题描述
CodeFamer正在开发一款游戏，它叫做开门游戏。在这个游戏中，玩家要打开一些门才能赢得这个游戏。在每一扇门上有一个问题，如果玩家可以答对门上的问题那么门就会打开。对于每一扇门，会有两个整数n和k。
门上有一些字，这样写道：
\[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）表示x的各位数字之和。例如DS(0)=0,DS(1)=1,DS(10254)=1+0+2+5+4=12. 如果你能够计算出S（n）,那么门就会打开，你就可以进入下一道门。
为了验证玩家的答案正确性，CodeFamer要写一个程序来生成正确答案。但是他正在忙于设计游戏的UI，所以他想请你来帮助他写这个程序。
你的任务就是，给定n,k计算出S（n）.
输入描述
多组测试数据。在输入文件的第一行是一个整数T，表示有T组数据。
在接下来的T行中，每一行含n和k，他们的含义在上边已经提到。
[参数约定]
所有输入项目均为整数。
1<= T <= 60000
0<=n<=100000000000000 (1e14)
1 <= K <= 1000
输出描述
对于每一个数据，输出占一行。输出格式是Case #id: ans， id是数据编号从1开始；ans是你要输出的结果。
看样例获得更多信息。
输入样例
2
2 2
3 5
输出样例
Case #1: 0
Case #2: 4
