Wrong Modulo

Andu made a terrible mistake! Just like the time he headed to Neamț and ended up in Târgu Neamț instead of Piatra Neamț, he made a similar mistake at school. He thought that $(a \cdot x) \ \% \ (a \cdot y) = x \ \% \ y$.

Task

Still curious, he asked himself: given two integers $N$ and $a$, how many pairs $(x, y)$ with $1 \leq x, y \leq N$ exist such that $(a \cdot x) \ \% \ (a \cdot y) = x \ \% \ y$?

Input data

Each test contains multiple test cases. The first line of input contains a single integer $T$, representing the number of test cases.

Each test case consists of one line, containing two space-separated integers $N$ and $a$.

Output data

For each test case, print the number of pairs $(x, y)$ that satisfy the conditions from the statement.

Constraints and clarifications

• $1 \leq T \leq 1 \ 000$
• $1 \leq N, a \leq 10^9$

Example

stdin

6
4 2
13 1
7 6
9 8
1 1000
1000000000 30030

stdout

8
169
16
23
1
20877697634

Explanation

In the first test case, the pairs that satisfy the conditions from the statement are: $(1,1)$, $(2,2)$, $(2,1)$, $(3,3)$, $(3,1)$, $(4,1)$, $(4,2)$ and $(4,4)$.

In the second test case, all $13^2=169$ pairs satisfy the conditions from the statement.