SP428 PARTPALI - Particular Palindromes

A palindromic decimal integer reads the same forward and backward. For example, the following numbers are palindromic. 6, 55, 282, 5005, 78187, 904409, 3160613, 11111111 Palindromic integers are plentiful. In fact, any integer not divisible by 10 has an infinite number of multiples that are palindromic. (The standard representation of a nonzero multiple of 10 cannot be palindromic since its reversal would have a leading 0.) Write a program to determine, for a given positive integer, how many of its positive multiples are palindromes of a given length.

The first line of the input will specify an integer n indicating the number of problem instances to follow, one to a line. Each of the ensuing n lines will specify a pair of positive integers m,s separated by a single space, with 1 < m < 1000, s < 20. (For m,s in this range, there are fewer than 2^32 palindromes among the s-digit multiples of m.) Each line will terminate with an end-of-line.

The output should indicate for each m,s, exactly how many s-digit positive palindromes are divisible by m, with one problem instance per line.