[백준 1963] 소수경로 (BFS) (C/C++)

#include <stdio.h>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
 
string startNum, endNum;
string digit = "0123456789"; // 자릿수 저장 
int T;
bool flag = false;
 
queue<string> q;
map<string, int> visited;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int check(string temp)
{
    int num = stoi(temp);
    
    for(int i = 2; i <= sqrt(num); i++)
    {
        if(num % i == 0)
        {
            return 0;
        }
    }
    
    return 1;
}
 
void BFS()
{
    visited[startNum] = 1;
    q.push(startNum);
    
    while(!q.empty())
    {
        string num = q.front();
        q.pop();
        
        if(num == endNum)
        {
            flag = true;
            return;
        }
        
        // 4 자리수 
        for(int i = 0; i < 4; i++)
        {
            string temp = num;
            
            // 첫째자리수 
            if(i == 0)
            {
                // 각 자리수 1~9 
                for(int j = 1; j <= 9; j++)
                {
                    // 교환 
                    temp[i] = digit[j];
                    
                    if(visited[temp] == 0 && check(temp) == 1)
                    {
                        visited[temp] = visited[num]+1;
                        q.push(temp);
                    }
                }
            }
            else
            {
                // 각 자리수 0~9 
                for(int j = 0; j <= 9; j++)
                {
                    // 교환
                    temp[i] = digit[j];
                    
                    if(visited[temp] == 0 && check(temp) == 1)
                    {
                        visited[temp] = visited[num]+1;
                        q.push(temp);
                    }
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1963_input.txt", "r", stdin);
    
    cin >> T;
    
    for(int n = 1; n <= T; n++)
    {
        queue<string> empty;
        swap(empty, q);
        visited.clear();
        flag = false;
        
        cin >> startNum >> endNum;        
        
        BFS();
        
        if(flag == false)
        {
            cout << "Impossible" << endl;
        }
        else
        {
            cout << visited[endNum]-1 << endl;
        }    
    }
    
    return 0;
}