#include<iostream>
#define l int64_t
#define c continue;
#define o(a) cout<<a<<endl;
#define r(i,x,y) for(l i=x;i<y;i++){
using namespace std;
int main(){l m=1e9+7,x,y,z,w,o,p,v[93],t[91][91][2],b;v[0]=1,v[1]=1;r(i,2,93)v[i]=v[i-1]+v[i-2];}r(i,2,91)r(j,1,i)b=v[i+1];if(j<2){t[i][0][0]=v[i],t[i][0][1]=b,t[i][j][0]=b,t[i][j][1]=2*b-v[i];c;}t[i][j][0]=t[i-1][j-1][1],t[i][j][1]=t[i-1][j-1][1]+t[i-1][j-1][0];}}cin>>b;while(b--){cin>>x>>y;if(x>y)swap(x,y);if(y<2){o("1 1")c}r(i,0,93)if(v[i]>x||v[i+1]>y){z=i-1,o(z)break;}}if(z<2){o(x*y%m)c}w=0;r(j,0,z)o=t[z][j][0],p=t[z][j][1];if(o>x||p>y)c w+=(y-p)/o+1;if(x>=p)w+=(x-p)/o+1;}o(w%m)}}