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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define x first
#define y second

namespace I_Wander___
{
	typedef long long ll;
	typedef std::pair<ll,ll> pii;
	const int N=233,MOD=1000000007;
	const ll INF=4000000000000000000ll;

	ll F[N];
	std::vector<pii> EF[N];

	int Q,tot;

	void dfs(pii A,int k)
	{
		EF[k].push_back(A);
		if(k+2==tot)return;

		pii B=pii(A.x+A.y,A.x);
		for(;B.x<=F[k+3];B.x+=B.y)
			dfs(B,k+1);
	}

	void initialize()
	{
		F[0]=F[1]=1;
		for(tot=1;F[tot]<INF;tot++)F[tot+1]=F[tot]+F[tot-1];
		dfs(pii(2,1),1),dfs(pii(3,1),1);
	}

	ll n,m;

	void solve()
	{
		scanf("%lld%lld",&n,&m);
		int k=std::upper_bound(F,F+tot+1,n)-F-1,dk=std::upper_bound(F,F+tot+1,m)-F-1;
		if(k==dk)k--;else k=std::min(k,dk);k+=k==0;

		ll ans=0;
		if(k==1)
		{
			if(n>m)std::swap(n,m);
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<i;j++)
					if(i%j==0)ans++;
				ans=(ans+m/i)%MOD;
			}
		}
		else 
		{
			for(auto A:EF[k-1])
			{
				if(n>=A.x && m>=A.y)
					ans=(ans+(m-A.y)/A.x)%MOD;
				if(m>=A.x && n>=A.y)
					ans=(ans+(n-A.y)/A.x)%MOD;
			}
		}
		ans=(ans%MOD+MOD)%MOD;
		printf("%d %lld\n",k,ans);
	}
}

int main()
{
//	freopen("in","r",stdin);
	I_Wander___::initialize();
	int T;
	for(scanf("%d",&T);T--;I_Wander___::solve());
	return 0;
}