/* Sample solution for NWERC'06: Prime Path
 * Author: Per Austrin
 * Algorithm: BFS
 */
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int main(void) {
  int pr[10000], dst[10000], n, a, b, B, d, v, nv;
  queue<int> q;
  for (memset(pr, 1, sizeof(pr)), n = 2; n < 10000; ++n) if (pr[n])
    for (a = n+n; a < 10000; a += n) pr[a] = 0;
  for (scanf("%d", &n); scanf("%d%d", &a, &b), n--; printf("%d\n", dst[b]-1))
    for (memset(dst, 0, sizeof(dst)), dst[a]=1, q.push(a); !q.empty(); q.pop())
      for (d = B = 1, v = q.front(); d < 5; ++d, B *= 10)
	for (int x = 0; nv = v+(x-v/B%10)*B, x < 10; ++x)
	  if (nv >= 1000 && pr[nv] && !dst[nv]) dst[nv] = dst[v]+1, q.push(nv);
  return 0;
}