It is very easy to find number of trailing zero in n! for a particular base b. In this problem you have to do the reverse. You have to find for how many bases b, n! has k trailing zeros in base b. Input Input starts with a positive number T ≤ 10000, denoting the number of test cases to follow. Each test case contains two non-negative integers, n ≤ 1015 and1≤k≤1015 inaline. Youmayassumethatn/k<500. Output For each input output one line containing the number of different bases. Print the solution modulo 1000000007 Sample Input 5 10 2 10 3 10 4 10 5 10 8 Sample Output Case 1: 24 Case 2: 0 Case 3: 4 Case 4: 0 Case 5: 1