Divisibility in the f‐Sequence

For any integer \( n\ge2 \), define \( g(n) \) to be the largest proper divisor of \( n \) (i.e. the greatest divisor less than \( n \)); for example, \( g(7)=1 \) and \( g(12)=6 \). Define

[ f(n)=n+g(n), ]

and for every \( m\ge0 \) define the \( m \)-th iterate of \( f \) by

[ f^{(0)}(n)=n, \quad f^{(m+1)}(n)=f( f^{(m)}(n) ). ]

Given several queries. In each query you are given two positive integers \( n \) (with \( n\ge2 \)) and \( k \). You are to find the smallest nonnegative integer \( m_0 \) such that for every \( m\ge m_0 \) the following divisibility holds:

[ f^{(m)}(n)\mid f^{(m+k)}(n). ]

If no such \( m_0 \) exists, output \( -1 \).

Note: Since for any \( n\ge2 \) we always have \[ f(n)=n+\frac{n}{p} = n\cdot\frac{p+1}{p} \quad \text{where} \; p=\min\{q:\;q\;\text{is a prime factor of}\; n\}, \]

each step multiplies \( n \) by a rational number. A short analysis of the powers of \( 2 \) in the factorization shows that, in the eventual behavior, the divisibility \( f^{(m)}(n)\mid f^{(m+k)}(n) \) will hold for all large \( m \) if and only if \( k \) is a multiple of \( 3 \). In that case the sequence enters a 3‐term parity cycle (when one looks only at whether \( f^{(m)}(n) \) is odd or even) and a short simulation will reveal the first index \( m_0 \) at which the cycle starts. Otherwise the answer is \( -1 \).

Input Format: The first line contains an integer \( T \) denoting the number of queries. Then \( T \) lines follow, each containing two positive integers \( n \) and \( k \) separated by spaces.

Output Format: For each query, output the corresponding answer \( m_0 \) in one line.

inputFormat

The first line contains an integer \( T \) indicating the number of test cases. Each of the following \( T \) lines contains two integers \( n \) (with \( n\ge2 \)) and \( k \), separated by a space.

Example:

5
3 3
7 3
2 1
12 6
8 4

outputFormat

For each test case, output the smallest nonnegative integer \( m_0 \) such that for every \( m\ge m_0 \), \( f^{(m)}(n) \) divides \( f^{(m+k)}(n) \). If no such \( m_0 \) exists, output \( -1 \).

Example:

0
3
-1
2
-1

sample

5
3 3
7 3
2 1
12 6
8 4

0
3
-1
2
-1