need help in volatile roy problem

Problem link : Contest Page | CodeChef

Please help, it’s high time.

Showing TLE for my code :
“”"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl “\n”
#define mod 1000000007
#define MAXN 100005

void swap(int& x, int& y)
{int temp = x; x = y; y = temp;}

vector adj[9];

bool chk(int x)
{
for(int i = 2; i<x; i++)
{
if(x%i==0)
return false;
}
return true;
}

int solve()
{
string s;
int x, y;
for(int i = 0; i<9; i++)
{
cin>>x;
s += ‘0’ + x;
}

adj[0].push_back(1);
adj[0].push_back(3);
adj[1].push_back(2);
adj[1].push_back(4);
adj[2].push_back(5);
adj[3].push_back(4);
adj[3].push_back(6);
adj[4].push_back(5);
adj[4].push_back(7);
adj[5].push_back(8);
adj[6].push_back(7);
adj[7].push_back(8);

string temp = “123456789”;

queue q;
q.push(s);
int ans = 0;
int size;
string t;
set st;
while(!q.empty())
{
ans++;
size = q.size();
for(int j = 0; j<size; j++)
{
auto p = q.front();
q.pop();

     if(p==temp)
        return ans-1;

     for(int i = 0; i<9; i++)
     {
        t = p;
        x = t[i] - '0';
        for(auto it : adj[i])
        {  
           y = t[it] - '0';
           if(chk(x+y))
           {
              swap(t[i], t[it]);
              if(st.find(t)==st.end())
                 q.push(t);
           }
        }
     }
  }

}
return -1;
}

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int t = 1;
cin>>t;
while(t–)
{
int x = solve();
cout<<x<<endl;
}
return 0;
}
“”"