H. Shiori Miyagi and Maximum Array Score
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
"Are you stupid, Sendai-san?"
— Shiori Miyagi

For the cost of 5000 yen, Miyagi can ask Sendai to do whatever she wants! Today, Miyagi demands that Sendai make her an array... specifically, Miyagi only wants a very particular type of array.

For arbitrary integers $$$b\geq 2$$$ and $$$x\geq 1$$$, define $$$v(b, x)$$$ to be the maximal $$$k$$$ satisfying $$$b^k \mid x$$$; that is, the maximal $$$k$$$ such that $$$x$$$ is a multiple of $$$b^k$$$. It can be shown that this is always a well-defined, nonnegative integer.

You are given integers $$$n$$$ and $$$m$$$ satisfying $$$n\leq m$$$. Find the maximum value of $$$\sum_{i=2}^n v(i, a_i)$$$ across all arrays $$$a$$$ of length $$$n$$$ satisfying the following conditions:

  • $$$a$$$ is strictly increasing; that is, for all $$$1\leq i\leq n-1$$$, $$$a_i \lt a_{i+1}$$$, and
  • for all $$$1\leq i\leq n$$$, $$$1\leq a_i\leq m$$$.
Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$)  — the number of test cases.

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2\leq n\leq m \leq 2\cdot 10^5$$$).

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output a single integer, the maximum value of $$$\sum_{i=2}^n v(i, a_i)$$$ across all arrays $$$a$$$ of length $$$n$$$ satisfying the given conditions.

Example
Input
6
4 20
6 6
6 216
3 500
2 8
5 29
Output
7
5
19
13
3
9
Note

In the first example, one possible array is $$$a = [6, 8, 9, 16]$$$ which yields a value of $$$3 + 2 + 2 = 7$$$.

It can be shown that this is the maximum value of $$$\sum_{i=2}^n v(i, a_i)$$$ across all arrays $$$a$$$ of length $$$n$$$ satisfying the given conditions.