#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
void multiply(ll m1[2][2],ll m2[2][2])
{
ll mult[2][2];
for(ll i=0;i<2;i++)
{
for(ll j=0;j<2;j++)
{
mult[i][j]=0;
for(ll k=0;k<2;k++)
{
mult[i][j]+=((m1[i][k])%mod * (m2[k][j])%mod)%mod;
}
}
}
for(ll i=0;i<2;i++)
{
for(ll j=0;j<2;j++)
{
m1[i][j]=mult[i][j];
}
}
}
void fibb(ll F[2][2],ll N)
{
if(N==0)
{
return;
}
ll b[2][2]={{1,1},{1,0}};
while(N)
{
if(N&1)
{
multiply(F,b);
}
multiply(b,b);
N>>=1;
}
}
ll findsum(ll N,ll M)
{
ll F[2][2]={{1,0},{0,1}};
fibb(F,M+1);
ll q=F[0][0];
ll Q[2][2]={{1,0},{0,1}};
fibb(Q,N);
ll p=Q[0][0];
p=(mod-p)%mod;
return (q+p)%mod;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--)
{
ll N,M;
cin>>N>>M;
cout<<findsum(N,M)<<endl;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBtb2QgMTAwMDAwMDAwNwoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgbXVsdGlwbHkobGwgbTFbMl1bMl0sbGwgbTJbMl1bMl0pCnsKICAgIGxsIG11bHRbMl1bMl07CiAgICBmb3IobGwgaT0wO2k8MjtpKyspCiAgICB7CiAgICAgICAgZm9yKGxsIGo9MDtqPDI7aisrKQogICAgICAgIHsKICAgICAgICAgICAgbXVsdFtpXVtqXT0wOwogICAgICAgICAgICBmb3IobGwgaz0wO2s8MjtrKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIG11bHRbaV1bal0rPSgobTFbaV1ba10pJW1vZCAqIChtMltrXVtqXSklbW9kKSVtb2Q7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBmb3IobGwgaT0wO2k8MjtpKyspCiAgICB7CiAgICAgICAgZm9yKGxsIGo9MDtqPDI7aisrKQogICAgICAgIHsKICAgICAgICAgICAgbTFbaV1bal09bXVsdFtpXVtqXTsKICAgICAgICB9CiAgICB9Cn0KCnZvaWQgZmliYihsbCBGWzJdWzJdLGxsIE4pCnsKICAgIGlmKE49PTApCiAgICB7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgbGwgYlsyXVsyXT17ezEsMX0sezEsMH19OwogICAgd2hpbGUoTikKICAgIHsKICAgICAgICBpZihOJjEpCiAgICAgICAgewogICAgICAgICAgICBtdWx0aXBseShGLGIpOwogICAgICAgIH0KICAgICAgICBtdWx0aXBseShiLGIpOwogICAgICAgIE4+Pj0xOwogICAgfQp9CgpsbCBmaW5kc3VtKGxsIE4sbGwgTSkKewoKICAgIGxsIEZbMl1bMl09e3sxLDB9LHswLDF9fTsKICAgIGZpYmIoRixNKzEpOwogICAgbGwgcT1GWzBdWzBdOwogICAgbGwgUVsyXVsyXT17ezEsMH0sezAsMX19OwogICAgZmliYihRLE4pOwogICAgbGwgcD1RWzBdWzBdOwogICAgcD0obW9kLXApJW1vZDsKICAgIHJldHVybiAocStwKSVtb2Q7Cn0KCmludCBtYWluKCkKewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKE5VTEwpOwogICAgbGwgdDsKICAgIGNpbj4+dDsKICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBsbCBOLE07CiAgICAgICAgY2luPj5OPj5NOwogICAgICAgIGNvdXQ8PGZpbmRzdW0oTixNKTw8ZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==