Dividing Products

All submissions for this problem are available.
Dr. Bobo, while working in his laboratory, thought of an interesting problem. He has spent considerable time trying to find a solution but in vain. So he turns to you to find the solution using your special powers of coding.
For a positive integer N, he defines a function DIVPRO(N) as follows.
 Let N be Ldigit number and n_{i} is the ith digit in the decimal representation of N (i = 1, 2, ..., L). So we can write N = n_{1}n_{2}...n_{L}.
 Then DIVPRO(N) = n_{1} / n_{2} * n_{3} / n_{4} * ... (i.e., we alternate division and multiplication of digits).
 The result is calculated from left to right.
 Division here is performed in standard mathematical way, so the result of the division can be noninteger number.
 If division by 0 occurs at any point for a given N, then DIVPRO(N) is undefined in such a case.
Let's consider some examples:
 DIVPRO(1) = 1. In fact, DIVPRO(N) = N for any 1digit number N.
 DIVPRO(42) = 4 / 2 = 2 is an integer.
 DIVPRO(123) = 1 / 2 * 3 = 3 / 2 = 1.5 is noninteger.
 DIVPRO(370) = 3 / 7 * 0 = 0, while intermediate result was 3 / 7 which is noninteger.
 DIVPRO(3465009) = 3 / 4 * 6 / 5 * 0 / 0 * 9 is undefined since we have division by zero.
Now Dr. Bobo would like to know how many Ldigit numbers have their DIVPRO value equal to V and he wants your help. Since this number can be quite large output it modulo 2^{32}, that is, you need to find the remainder of the division of the answer by 2^{32}.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The only line of each test case contains two spaceseparated integers L and V.
Output
For each test case, output a single line containing the number of Ldigit positive integers, whose DIVPRO value is V. As was mentioned above you should print this number modulo 2^{32}.
Constraints
 1 ≤ T ≤ 320000 (320 thousands)
 1 ≤ L ≤ 36
 0 ≤ V < 10^{18}
Example
Input: 4 2 0 3 27 5 24 10 45 Output: 0 5 486 2349595
Explanation
Example case 1. No 2digit number has DIVPRO value of 0 (as leading zeros are not allowed). Hence the answer is zero.
Example case 2. The only 3digit numbers having DIVPRO value of 27 are 319, 629, 913, 926 and 939. So there are 5 such numbers in all.
Warning!
The input file size could reach 7MB so be sure you are using fast I/O method.
Author:  viv001 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/DIVPRO 
Tags  dynamicprogramming, jan13, medium, viv001 
Date Added:  28082012 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions