Problem: Kenus, the organizer of International Euclidean Olympiad, is seeking a pair of two integers that requires many steps to find its greatest common divisor using the Euclidean algorithm.

You are given Q queries. The i-th query is represented as a pair of two integers X_i and Y_i, and asks you the following: among all pairs of two integers (x,y) such that 1 ≤ x ≤ X_i and 1 ≤ y ≤ Y_i, find the maximum Euclidean step count (defined below), and how many pairs have the maximum step count, modulo 10^9+7.

Process all the queries. Here, the Euclidean step count of a pair of two non-negative integers (a,b) is defined as follows:

* (a,b) and (b,a) have the same Euclidean step count.
* (0,a) has a Euclidean step count of 0.
* If a > 0 and a ≤ b, let p and q be a unique pair of integers such that b=pa+q and 0 ≤ q < a. Then, the Euclidean step count of (a,b) is the Euclidean step count of (q,a) plus 1.

Constraints

* 1 ≤ Q ≤ 3 × 10^5
* 1 ≤ X_i,Y_i ≤ 10^{18}(1 ≤ i ≤ Q)

Input

The input is given from Standard Input in the following format:


Q
X_1 Y_1
:
X_Q Y_Q


Output

For each query, print the maximum Euclidean step count, and the number of the pairs that have the maximum step count, modulo 10^9+7, with a space in between.

Examples

Input

3
4 4
6 10
12 11


Output

2 4
4 1
4 7


Input

10
1 1
2 2
5 1000000000000000000
7 3
1 334334334334334334
23847657 23458792534
111111111 111111111
7 7
4 19
9 10


Output

1 1
1 4
4 600000013
3 1
1 993994017
35 37447
38 2
3 6
3 9
4 2

Solution (in CPP):

Solution:
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=110,P=1000000007;
const ll oo=1000000000000000000ll;
int a,i,j,k,n,m,ch,Test,nm;
int nn[N];
ll t,x,y,ans,ta,tb;
ll fib[N];
struct cc { ll a,b;} A[N][N];
void R(ll &x) {
	x=0;ch=getchar();
	while (ch<'0' || '9'<ch) ch=getchar();
	while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar();
}
void W(ll x) {
	if (x>=10) W(x/10);
	putchar(x%10+'0');
}
ll min(ll x,ll y) {
	if (x<y) return x;
	return y;
}
bool check(ll a,ll b,int c) {
	//printf("%lld %lld %d\n",a,b,c);
	if (!c) return 1;
	if (a==0) {
		if (c==1) {
			if (b>x) return 0;
			return 1;
		}
		a=b;b=a+b;
		if (a>x || b>y) return 0;
		c--;
	}
	while (c) {
		ll t=a;a=b;b=t+b;
		if (b%a!=t) return 0;
		if (a>x || b>y) return 0;
		c--;
	}
	return 1;
}
void dfs(ll a,ll b,int c) {
	//if (i==5) printf("%lld %lld %d\n",a,b,c);
	if (c==1) {
		nn[i]++;
		A[i][nn[i]].a=b;
		A[i][nn[i]].b=a+b;
		return;
	}
	if (a==0) {
		if (check(b,b,c-1)) dfs(b,b,c-1);
		a=b;
	}
	for (ll i=a+b;i<=y;i+=b) {
		if (check(b,i,c-1)) dfs(b,i,c-1);
		else break;
	}
}
int main() {
	fib[0]=0;
	fib[1]=1;
	nm=1;
	while (fib[nm]<=oo) {
		nm++;
		fib[nm]=fib[nm-2]+fib[nm-1];
	}
	for (i=2;i+2<=nm;i++) {
		x=fib[i+1];y=fib[i+2];
		for (j=1;j<=y;j++) {
			if (check((ll) 0,(ll) j,i-1)) dfs(0,j,i-1);
			else break;
		}
	}
	scanf("%d",&Test);
	while (Test--) {
		R(x);R(y);ans=0;
		if (x==1 && y==1) {
			puts("1 1");
			continue;
		}
		if (x>y) {
			t=x;x=y;y=t;
		}
		a=0;
		while (fib[a+1]<=x && fib[a+2]<=y) a++;
		for (i=1;i<=nn[a];i++) {
			ta=A[a][i].a;
			tb=A[a][i].b;
			//printf("%lld %lld\n",ta,tb);
			if (ta<=x && tb<=y) ans=((y-tb)/ta+1+ans)%P;
			if (ta<=x && tb<=x) ans=((x-tb)/ta+1+ans)%P;
		}
		if (a==2) ans=(ans+P-x)%P;
		W(a-1);putchar(' ');W(ans);puts("");
	}
}