There are only 1061 4-digit primes. Generate a graph with each vertex representing one of these primes. Add edges between two vertices if we can move from one vertex(prime) to another with a cost of 1.

Notice that there can be atmost 39 edges per vertex so the number edges is O(n). Then, since the number of test cases are small and the cost for each edge is same, a simple bfs from the initial prime as the root should do the trick for each test case.