Under construction

Still being built. Things may change

Finger Snap

Interview

Time limit2sMemory limit512 MB

Summary
Starting from N, use halve, third, increment, and decrement operations to reach a prime in [A, B] with the fewest operations, or report -1.
Level

Medium6 of 10

Topics
BFS, Number theory, Math, Graph
Solved
No attempts yet

Problem

Even people who have not watched the [Avengers] series know what the ‘Infinity Gauntlet’ is. For those who do not, here is the explanation: if you wear the Infinity Gauntlet with all the Infinity Stones gathered and snap your fingers, you can do whatever you want. However, the recoil is so severe that you cannot use it very many times.

The mad mathematician Sonaht happens to get his hands on this Infinity Gauntlet. But this Infinity Gauntlet has a slight defect, so there are only a few things a finger snap can do. The following lists what a finger snap can do.

  1. Halve the number of living things in the entire universe.
  2. Reduce the number of living things in the entire universe to 1/3 of the current number.
    (In the two cases above, if the division is not exact, keep only the quotient and discard the remainder.)
  3. Increase the number of living things in the entire universe by one.
  4. Decrease the number of living things in the entire universe by one.
    (This cannot be done if the number of living things in the entire universe is already 0.)

Sonaht wants to reduce the number of living things in the entire universe to at least A and at most B. But, true to being a mad mathematician, among the numbers at least A and at most B, he wants to make it a prime. (Perhaps there is no prime between A and B.) A prime is a number whose only distinct divisors are 1 and itself. However, since the Infinity Gauntlet has severe recoil, Sonaht wants to achieve this goal with as few finger snaps as possible. Find the minimum number of finger snaps Sonaht needs.

Input

The first line gives the number of test cases T. (1 ≤ T ≤ 10)

From the second line, across T lines, the current number of living things in the entire universe, a natural number N, and Sonaht's target range, natural numbers A, B, are given separated by spaces. (2 ≤ N ≤ 1,000,000, 2 ≤ A ≤ B ≤ 100,000)

Output

For each line, print the minimum number of finger snaps Sonaht needs to make the number of living things in the entire universe a prime within the target range for each test case.

If it cannot be made a prime within the target range, print -1.

Each test case must be considered independently.

Examples1

  1. Example 1

    Input
    5
9 2 4
100000 605 610
300 14 16
7 7 10
98765 500 550
    Expected output
    1
15
-1
0
12