Yukikaze is learning number theory. In number theory, a k-smooth number is an integer whose prime factors are all less or equal to k. Given nand k, she wants to know how many k-smooth numbers are less or equal to n.
输入格式
The input contains several test cases, and the first line contains a single integer T(1≤T≤50), the number of test cases. Each of the next T lines contains two integers n(1≤n≤109),k(1≤k≤109), denoting the question described above.
输出格式
For each test case, output the answer in a single line.