The two versions are different problems. You may want to read both versions. You can make hacks only if both versions are solved.

You are given two positive integers $n$, $m$.

Calculate the number of ordered pairs $(a, b)$ satisfying the following conditions:

• $1\le a\le n$, $1\le b\le m$;
• $a+b$ is a multiple of $b \cdot \gcd(a,b)$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$, $m$ ($1\le n,m\le 2 \cdot 10^6$).

It is guaranteed that neither the sum of $n$ nor the sum of $m$ over all test cases exceeds $2 \cdot 10^6$.

Output

For each test case, print a single integer: the number of valid pairs.

Note

In the first test case, only $(1,1)$ satisfies the conditions.

In the fourth test case, $(1,1),(2,1),(2,2),(3,1),(4,1),(5,1),(6,1),(6,2),(6,3),(7,1),(8,1),(9,1),(10,1),(10,2)$ satisfy the conditions.