Description

Viznan has an instant-kill skill, but its activation condition is demanding.

Let $d(n)$ denote the number of positive divisors of $n$. When facing an enemy with $x$ health points, the amount of damage Viznan must deal to activate the skill is

Given $x$ and $y$, calculate the required amount of damage.

Input Format

This problem contains multiple test cases.

The first line contains two integers $T$ and $id$, where $T$ is the number of test cases and $id$ is the test-data identifier. The value of $id$ does not affect the answers.

Each of the next $T$ lines contains two integers $x$ and $y$, describing one test case.

Output Format

For each test case, output the value of $\max\limits_{1\leq i\leq y} d(x\cdot i)$ on a separate line.

Sample

Input #1

3 0
5 5
10 5
6 10

Output #1

6
8
12

Sample Explanation

For the first test case, $d(5)=2$, $d(10)=4$, $d(15)=4$, $d(20)=6$, and $d(25)=3$. Therefore, the answer is $6$.

For the second test case, $d(10)=4$, $d(20)=6$, $d(30)=8$, $d(40)=8$, and $d(50)=6$. Therefore, the answer is $8$.

For the third test case, $d(6)=4$, $d(12)=6$, $d(18)=6$, $d(24)=8$, $d(30)=8$, $d(36)=9$, $d(42)=8$, $d(48)=10$, $d(54)=8$, and $d(60)=12$. Therefore, the answer is $12$.

Constraints

For all test cases:

• $1\leq T\leq 10$;
• $1\leq x,y\leq 10^{10}$.