#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
bool sieve[1000000]={0};
for(int i=2;i*i<=1000000;i++) {
if(!sieve[i]) {
for(int j=2*i;j<=1000000;j+=i) {
sieve[j]=true;
}
}
}
int n;
cin>>n;
for(int i=0;i<n;i++) {
int a,b,c;
int count=0;
cin>>a>>b;
if(!sieve[a]) {
count++;
}
if(!sieve[b]) {
count++;
}
for(int j=3;j<=20;j++) {
c=a+b;
if(!sieve[c]) {
count++;
}
a=b;
b=c;
}
cout<<count<<'\n';
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgY29uc3QgKmFyZ3ZbXSkKewogICAgYm9vbCBzaWV2ZVsxMDAwMDAwXT17MH07CiAgICBmb3IoaW50IGk9MjtpKmk8PTEwMDAwMDA7aSsrKSB7CiAgICAgIGlmKCFzaWV2ZVtpXSkgewogICAgICAgIGZvcihpbnQgaj0yKmk7ajw9MTAwMDAwMDtqKz1pKSB7CiAgICAgICAgICBzaWV2ZVtqXT10cnVlOwogICAgICAgIH0KICAgICAgfQogICAgfQogICAgaW50IG47CiAgICBjaW4+Pm47CiAgICBmb3IoaW50IGk9MDtpPG47aSsrKSB7CiAgICAgICAgaW50IGEsYixjOwogICAgICAgIGludCBjb3VudD0wOwogICAgICAgIGNpbj4+YT4+YjsKICAgICAgICBpZighc2lldmVbYV0pIHsKICAgICAgICAgICAgY291bnQrKzsKICAgICAgICB9CiAgICAgICAgaWYoIXNpZXZlW2JdKSB7CiAgICAgICAgICAgIGNvdW50Kys7CiAgICAgICAgfQogICAgICAgIGZvcihpbnQgaj0zO2o8PTIwO2orKykgewogICAgICAgICAgICBjPWErYjsKICAgICAgICAgICAgaWYoIXNpZXZlW2NdKSB7CiAgICAgICAgICAgICAgICBjb3VudCsrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGE9YjsKICAgICAgICAgICAgYj1jOwogICAgICAgIH0KICAgICAgICBjb3V0PDxjb3VudDw8J1xuJzsKICAgIH0KICAgIHJldHVybiAwOwp9