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<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define pb push_back

using namespace std;
const int N=105;
typedef long long LL;
const int mod=1000000007;
LL x,y,f[N];
int ans,tot;
struct data{LL a,b;};
vector <data> vt[N];

int getint()
{
	char ch;
	while(!isdigit(ch=getchar()));
	int x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x;
}

LL getLL()
{
	char ch;
	while(!isdigit(ch=getchar()));
	LL x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x;
}

void dfs(int x,LL a,LL b)
{
	if(x>88) return;
	if(a>=f[x] && b>=f[x+1]) return;
	vt[x].pb((data){a,b});
	dfs(x+1,b,a+b);
	dfs(x+1,b,a+2*b);
}

void solve()
{
	x=getLL(),y=getLL(),ans=tot=0;
	if(x>y) swap(x,y);
	rep(i,1,90) if(f[i]>x || f[i+1]>y) {ans=i-1; break;}
	if(ans<=1)
	{
		if(x==1) tot=y%mod;
		else tot=4;
		printf("%d %d\n",1,tot);
		return;
	}

	int sz=vt[ans].size();
	rep(i,0,sz-1)
	{
		LL a=vt[ans][i].a,b=vt[ans][i].b;
		if(a<=x && b<=y) tot=(tot+(x-a)/b)%mod;
		if(a<=y && b<=x) tot=(tot+(y-a)/b)%mod;
	}
	printf("%d %d\n",ans,tot);
}

int main()
{
	f[0]=f[1]=1;
	rep(i,2,90) f[i]=f[i-1]+f[i-2];
	dfs(1,1,1);
	for(int T=getint(); T--; solve());
	return 0;
}