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<bits/stdc++.h>
using namespace std;
#define LL long long
#define X first
#define Y second

void read(LL &x)
{
	char c=getchar(); x=0;
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
}

const int N=1000;
int T;
LL n,m;
pair<LL,LL> ex[90][90]; //excellent

int main()
{
#ifdef h10
	freopen("F.in","r",stdin);
	freopen("F.out","w",stdout);
#endif
	int i,j,k;
	ex[1][0]=make_pair(1,2);
	for (i=1;i<87;i++)
	{
		for (j=0;j<i;j++)
			ex[i+1][j]=make_pair(ex[i][j].Y,ex[i][j].X+ex[i][j].Y);
		ex[i+1][i]=make_pair(ex[i][0].X+ex[i][0].Y,ex[i][0].X+ex[i][0].X+ex[i][0].Y);
	}

	scanf("%d",&T);
	while (T--)
	{
		LL cnt=0;
		read(n); read(m);
		if (n>m) swap(n,m);
		for (k=2;k<=87;k++)
			if (ex[k][0].X>n||ex[k][0].Y>m) break;
		k--;
		for (i=0;i<k;i++)
		{
			if (ex[k][i].X<=n&&ex[k][i].Y<=m)
				cnt+=1+((m-ex[k][i].Y)/ex[k][i].X);
			if (ex[k][i].X<=m&&ex[k][i].Y<=n)
				cnt+=1+((n-ex[k][i].Y)/ex[k][i].X);
		}
		cnt+=k==1&&n>=1&&m>=1;
		cnt+=k==1&&n>=2&&m>=2;
		printf("%d %lld\n",k,cnt%1000000007);
	}
}