# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* abhi_inav

*tabr, iceknight1093*

**Testers:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

You start with an integer X. In one move, you add to X its smallest prime factor.

How many moves till your integer is at least Y?

# EXPLANATION:

If X is even, its smallest prime factor is 2; and X+2 is also even so this will continue to be the case from here on.

Since we’re adding exactly 2 at each step, the number of steps needed to reach Y is quite easy to calculate:

- Let d = Y-X be the distance between X and Y.
- Each step shortens this distance by 2, so we need \displaystyle \left\lceil \frac{d}{2} \right\rceil steps, where \left\lceil \ \right\rceil denotes the ceiling function.

This can be computed in \mathcal{O}(1).

If X is odd, then its smallest prime factor is an odd number.

However, on adding this odd number to X, the resulting number is even!

So, we have the following solution:

- If X is even, solve directly in \mathcal{O}(1)
- If X is odd, perform the first move manually. Now X is even, so again it can be solved for in $\mathcal{O}(1).

# TIME COMPLEXITY

\mathcal{O}(1) per test case.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
x, y = map(int, input().split())
ans = 0
if x%2 == 1:
ans = 1
for i in range(2, x+1):
if x%i == 0: # smallest non-1 factor is also smallest prime factor
x += i
break
print(ans + (y-x+1)//2)
```