eolymp
bolt
Try our new interface for solving problems
Problems

How to Glue a Number?

How to Glue a Number?

Time limit 2 seconds
Memory limit 64 MiB

You are given all positive integers in the range from 10 to 99 inclusive. Find the number of ways to choose from them exactly k different numbers (selection order is important) so that after gluing them in one big line, the resulting number is divisible by x.

Input data

The first line contains the number of test cases t (1t100). Each test case is given in a separate line and contains two numbers: k (1k5) and x (1x100), separated by a space.

Output data

For each test case print the answer in a single line according to format specified in example.

Examples

Input example #1
3
2 17
1 5
3 21
Output example #1
Case #1: 471
Case #2: 18
Case #3: 33726
Source The 2012 All-Ukrainian Collegiate Programming Contest Round I Training Contest 19 April 2012