RoAlgo PreOJI 2024 XI-XII | Morcovi

Task

Andrei has $n$ carrots, conveniently numbered from $1$ to $n$, and a favorite number $k$.

Two carrots $a$ and $b$ are compatible if $gcd(a,b) + k = lcm(a,b)$, where:

• $gcd(a,b)$ represents the greatest common divisor of the numbers $a$ and $b$;
• $lcm(a,b)$ represents the least common multiple of the numbers $a$ and $b$.

In how many ways can Andrei choose two carrots $a$ and $b$ ($1 \le a < b \le n$) such that they are compatible?

Input data

Each test contains multiple test cases. On the first line of the input file morcovi.in will be the number of test cases $t$.

Each test case consists of two numbers $n$ and $k$ — the number of Andrei's carrots and Andrei's favorite number, respectively.

Output data

For each test case, print the number of ways Andrei can choose two carrots $a$ and $b$ ($1 \le a < b \le n$) such that they are compatible in the output file morcovi.out.

Constraints and clarifications

• $1 \le t \le 100$
• $1 \le n,k \le 10^9$
• To obtain points for a particular subtask, at least one submitted source code will have to pass all the tests of that subtask.

Example

morcovi.in

5
1000000000 1
30 6
6 10
420 69
123456789 987654321

morcovi.out

1
4
1
8
54

Explanation

• In the first test case, the only way to choose the carrots is $a=1$ and $b=2$.
• In the second test case, the $4$ ways to choose the carrots are: $(1,7)$, $(2,8)$, $(3,9)$, and $(6,12)$.
• In the third test case, the only way to choose the carrots is $a=4$ and $b=6$.
• In the fourth test case, the $8$ ways to choose the carrots are: $(1,70)$, $(2,35)$, $(3,72)$, $(5,14)$, $(7,10)$, $(9,24)$, $(23,92)$, and $(69,138)$.