이번 문제는 에라토스테네스의 체를 통해 소수 리스트를 생성하고, BFS를 통해 핑거스냅으로 일어날 수 있는 수의 모든 변화를 탐색하는 방식으로 해결하였다. 인덱스 에러가 발생하여 문제를 다시 보니 n의 범위가 1,000,000이었는데 범위를 100,000로 잡아 발생한 문제였고, 이를 수정하여 해결하였다.

Code

import math
from collections import deque
t = int(input())
primes = [True for _ in range(1000001)]
for i in range(2, int(math.sqrt(1000001))+1):
    if primes[i]:
        for j in range(i+i, 1000001, i):
            primes[j] = False
def finger_snap(cur):
    q = deque()
    q.append((cur, 0))
    visited = [False for _ in range(1000001)]
    visited[cur] = True
    while q:
        num, cnt = q.popleft()
        if a <= num <= b and primes[num]:
            return cnt
        nxt = num//2
        if 0 <= nxt < 1000001 and not visited[nxt]:
            visited[nxt] = True
            q.append((nxt, cnt+1))
        nxt = num//3
        if 0 <= nxt < 1000001 and not visited[nxt]:
            visited[nxt] = True
            q.append((nxt, cnt + 1))
        nxt = num+1
        if 0 <= nxt < 1000001 and not visited[nxt]:
            visited[nxt] = True
            q.append((nxt, cnt+1))
        if num > 0:
            nxt = num-1
            if 0 <= nxt < 1000001 and not visited[nxt]:
                visited[nxt] = True
                q.append((nxt, cnt + 1))
    return -1
for _ in range(t):
    n, a, b = map(int, input().split())
    flag = False
    for i in range(a, b+1):
        if primes[i]:
            flag = True
            break
    if not flag:
        print(-1)
    else:
        print(finger_snap(n))