Cho một số \(n\) được biểu diễn theo cơ số \(b\). Các chữ số của số này đều khác nhau đôi một.

Hãy đếm số hoán vị của số này theo cơ số \(b\) sao cho hoán vị này có giá trị theo cơ số \(10\) chia hết cho \(k\).

Input

• Số nguyên dương \(q\) --- số câu hỏi
• Mỗi câu hỏi chứa hai số nguyên dương \(b\), \(k\) và số \(n\) được biểu diễn theo cơ số \(b\)

Constraints

• \(q \leq 100\)
• \(2 \leq b \leq 16\)
• \(1 \leq k \leq 20\)

Output

• Với mỗi test case, in ra một dòng dạng Case X: Y trong đó \(X\) là số thứ tự test case và \(Y\) là số hoán vị thỏa mãn đề bài

Example

3
2 2
10
10 2
5681
16 1
ABCDEF0123456789

Case 1: 1
Case 2: 12
Case 3: 20922789888000

Tham khảo: LightOJ