Migrated from Lutece 1497 D

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Little Ruins is playing a number game, first he chooses two positive integers $y$ and $K$ and calculates $f(y,K)$, here

$$f(y, K) = \sum_{z\text{ in every digits of }y} z^K $$

e.g.

$$f(233, 2) = 2^2 + 3^2 + 3^2 = 22$$

then he gets the result

$$x = f(y, K) - y$$

As Ruins is forgetful, a few seconds later, he only remembers $K$, $x$ and forgets $y$. please help him find how many $y$ satisfy $x=f(y,K)-y$.

Input

First line contains an integer $T$ ($1\le T\le 100$), which indicates the number of test cases.

Every test case contains one line with two integers $x$, $K$ ($0\le x\le 10^9,1\le K\le 9$).

Output

For every test case, you should output Case #x: y, where x indicates the case number and counts from $1$ and y is the result.

Samples

2
2 2
3 2

Case #1: 1
Case #2: 2

Resources

第二届中国大学生程序设计竞赛 杭州站（CCPC 2016 Hangzhou Site）