Background

Problem Description

For $n \in \mathbb{Z_{\ge 2}}$, let $g(n)$ be the largest proper divisor of $n$ (the largest divisor less than $n$), for example, $g(7) = 1, g(12) = 6$.

Define $f(n) = n + g(n)$. Let $f^{(0)}(n)=n$, and for $m \in \mathbb{Z_{\ge 0}}$ we have $f^{(m+1)}(n)=f(f^{(m)}(n))$.

There are multiple queries. For each query, given positive integers $n,k$, find the smallest natural number $m_0$ such that for any $m \ge m_0$, we always have $f^{(m)}(n) \mid f^{(m+k)}(n)$.

If such an $m_0$ does not exist, let $m_0=-1$.

Input Format

The first line contains a positive integer $T$, the number of queries.

The next $T$ lines each contain two positive integers $n,k$, representing one query.

Output Format

For each query, output one integer as the answer.

2
2 3
3 4

0
-1

Hint

Sample Explanation

When $n=2,k=3$, $m_0=0$.

When $n=3,k=4$, there is no $m_0$ that satisfies the condition.

Constraints

This problem uses bundled testdata.

• Subtask $1$ ($1$ point): $T=k=1$.
• Subtask $2$ ($12$ points): $T,n,k \le 10$.
• Subtask $3$ ($24$ points): $T \le 10,n \le 10^5$.
• Subtask $4$ ($36$ points): $T \le 10^3$.
• Subtask $5$ ($27$ points): no special constraints.

For $100\%$ of the data, it is guaranteed that $1 \le T \le 2 \times 10^6$, $2 \le n \le 3 \times 10^7$, $1 \le k \le 10^9$.

Translated by ChatGPT 5