卡车牌照（两个方向二选一作答，非Python）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Main{
    static boolean[] prime;
    static{
        prePro();
    }
    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in), 1000000);
        int T = Integer.parseInt(sc.readLine());
        while(T-- > 0){
            String[] strs = sc.readLine().split(" ");
            System.out.println(h(Integer.parseInt(strs[0]), Integer.parseInt(strs[1])));
        }
    }
    private static void prePro(){
        int n = (int)1e6;
        prime = new boolean[n + 1];
        Arrays.fill(prime, true);
        for(int i = 2; i <= n; i++){
            if(prime[i]){
                for(int j = 2 * i; j <= n; j += i){
                    prime[j] = false;
                }
            }
        }
    }
    static int[] temp = {1, 10, 100, 1000, 10000, 100000, 1000000};
    private static int h(int n1, int n2){
        if(n1 == n2){
            return 0;
        }
        Set<Integer> seen = new HashSet<>();
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(n1);
        int step = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-- > 0){
                int num = queue.poll();
                //6 位进行改变
                for(int i = 0; i < 6; i++){
                    int cur = num / temp[i + 1] * temp[i + 1] + num % temp[i];
                    for(int j = 0; j <= 9; j++){
                        cur += j * temp[i];
                        if(cur == n2){
                            return step + 1;
                        }
                        if(prime[cur] && !seen.contains(cur)){
                            seen.add(cur);
                            queue.add(cur);
                        }
                        cur -= j * temp[i];
                    }
                }
            }
            step++;
        }
        return -1;
    }
}