I	All Your Bases Belong to us
	Input	Standard Input
	Output	Standard Output

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≤10¹⁵ and 1≤k≤10¹⁵ in a line. You may assume and n/k<500.

Output

For each input output one line containing the number of different bases. Print the solution modulo 1000000007

Sample Input	Sample Output
5 10 2 10 3 10 4 10 5 10 8	Case 1: 24 Case 2: 0 Case 3: 4 Case 4: 0 Case 5: 1