#include<bits/stdc++.h>
using namespace std;
#define MAXN	105
#define INF	1e18
#define P	1000000007
long long fib[MAXN];
vector<pair<long long, long long> > a[MAXN];
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int main(){
	fib[0] = fib[1] = 1;
	int tot = 1;
	while (true) {
		fib[tot + 1] = fib[tot] + fib[tot - 1];
		if (fib[tot + 1] > INF) break;
		tot++;
	}
	a[1].push_back(make_pair(1, 2));
	a[1].push_back(make_pair(1, 3));
	a[1].push_back(make_pair(1, 4));
	for (int i = 1; i <= tot - 3; i++) {
		for (unsigned j = 0; j < a[i].size(); j++) {
			long long x = a[i][j].first;
			long long y = a[i][j].second;
			x += y;
			while (x <= fib[i + 3] + fib[i]){
				a[i + 1].push_back(make_pair(y, x));
				x += y;
			}
		}
	}
	int q; read(q);
	while (q--){
		long long n, m;
		read(n), read(m);
		if (n > m) swap(n, m);
		int ans = 1;
		while (fib[ans + 1] <= n && fib[ans + 2] <= m)
			ans++;
		printf("%d ", ans);
		if (ans == 1) {
			printf("%lld\n", n * m % P);
			continue;
		}
		else {
			long long num = 0;
			for (unsigned j = 0; j < a[ans - 1].size(); j++) {
				long long x = a[ans - 1][j].first;
				long long y = a[ans - 1][j].second;
				if (x <= m && y <= n) num = (num + (m - x) / y) % P;
				if (x <= n && y <= m) num = (num + (n - x) / y) % P;
			}
			printf("%lld\n", num);
		}
	}
}