Problem Description

A positive proper divisor is a positive divisor of a number $n$, excluding $n$ itself. For example, 1, 2, and 3 are positive proper divisors of 6, but 6 itself is not.

Peter has two positive integers $n$ and $d$. He would like to know the number of integers below $n$ whose maximum positive proper divisor is $d$.

Input

There are multiple test cases. The first line of input contains an integer $T$ $(1 \le T \le 10^6)$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $d$ $(2 \le n, d \le 10^9)$.

Output

For each test case, output an integer denoting the answer.

9
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
100 13

1
2
1
0
0
0
0
0
4