#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
//#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

const double PI = acos(-1);
const double EPS = 1e-9;

const int MX = 1<<18;
const int MM = 1000000007;

const int L = 90;

ll F[105];
vector<pll> GP[L];

int main()
{
	F[0] = F[1] = 1;
	for(int i = 2; i <= L; i++){
		F[i] = F[i-1] + F[i-2];
	}

	GP[1].emplace_back(1, 2);
	GP[1].emplace_back(1, 3);

	for(int t = 2; t <= L; t++){
		for(pll e : GP[t-1]){
			ll a = e.first, b = e.second;
			while(b+a <= F[t+2]){
				a += b;
				GP[t].emplace_back(b, a);
			}
		}
	}

	int Q;
	scanf("%d", &Q);
	for(int t = 1; t <= Q; t++){
		ll X, Y;
		scanf("%lld%lld", &X, &Y);
		if( X > Y ) swap(X, Y);
		if( X == 1 || X == 2 && Y == 2 ){
			printf("1 %lld\n", X*Y%MM);
			continue;
		}
		if( X == 2 ){
			printf("2 %lld\n", (Y-1)/2%MM);
			continue;
		}
		int k = min(upper_bound(F, F+L+1, X) - F, upper_bound(F, F+L+1, Y) - F-1) - 1;
		ll ans = 0;
		auto f = [&](ll X, ll Y){
			for(pll e : GP[k-1]){
				if( e.second <= X ){
					ans = (ans + (Y - e.first) / e.second) % MM;
				}
			}
		};
		f(X, Y); f(Y, X);
		printf("%d %lld\n", k, ans);
	}
}

### Prompt

Construct a cpp code solution to the problem outlined:

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

### Response

```cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
//#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

const double PI = acos(-1);
const double EPS = 1e-9;

const int MX = 1<<18;
const int MM = 1000000007;

const int L = 90;

ll F[105];
vector<pll> GP[L];

int main()
{
	F[0] = F[1] = 1;
	for(int i = 2; i <= L; i++){
		F[i] = F[i-1] + F[i-2];
	}

	GP[1].emplace_back(1, 2);
	GP[1].emplace_back(1, 3);

	for(int t = 2; t <= L; t++){
		for(pll e : GP[t-1]){
			ll a = e.first, b = e.second;
			while(b+a <= F[t+2]){
				a += b;
				GP[t].emplace_back(b, a);
			}
		}
	}

	int Q;
	scanf("%d", &Q);
	for(int t = 1; t <= Q; t++){
		ll X, Y;
		scanf("%lld%lld", &X, &Y);
		if( X > Y ) swap(X, Y);
		if( X == 1 || X == 2 && Y == 2 ){
			printf("1 %lld\n", X*Y%MM);
			continue;
		}
		if( X == 2 ){
			printf("2 %lld\n", (Y-1)/2%MM);
			continue;
		}
		int k = min(upper_bound(F, F+L+1, X) - F, upper_bound(F, F+L+1, Y) - F-1) - 1;
		ll ans = 0;
		auto f = [&](ll X, ll Y){
			for(pll e : GP[k-1]){
				if( e.second <= X ){
					ans = (ans + (Y - e.first) / e.second) % MM;
				}
			}
		};
		f(X, Y); f(Y, X);
		printf("%d %lld\n", k, ans);
	}
}

```