#include <algorithm>
#include <utility>
#include <cstdio>
#include <vector>
#define pb push_back
#define MOD 1000000007
typedef long long ll;
ll F[105];
std::vector<std::pair<ll, ll> > vec[105];
int main()
{
	// freopen("AGC015-F.in", "r", stdin);
	int len = 2;
	F[0] = F[1] = 1;
	while (true)
	{
		F[len] = F[len - 1] + F[len - 2];
		if (F[len] > 2e18)
			break;
		len++;
	}
	vec[1].pb({1, 2});
	vec[1].pb({1, 3});
	for (int i = 1; i < len - 3; i++)
	{
		for (auto &it : vec[i])
		{
			auto x = it.first, y = it.second;
			while (x + y <= F[i + 3])
			{
				x += y;
				vec[i + 1].pb({y, x});
			}
		}
	}
	int cas;
	scanf("%d", &cas);
	while (cas--)
	{
		ll n, m;
		scanf("%lld%lld", &n, &m);
		if (n > m)
			std::swap(n, m);
		int ans = 1;
		while (ans + 2 < len && F[ans + 1] <= n && F[ans + 2] <= m)
			ans++;
		if (ans == 1)
			printf("1 %lld\n", n * m % MOD);
		else
		{
			ll cnt = 0;
			for (auto &it : vec[ans - 1])
			{
				auto x = it.first, y = it.second;
				if (y <= n)
					(cnt += (m - x) / y) %= MOD;
				if (y <= m)
					(cnt += (n - x) / y) %= MOD;
			}
			printf("%d %lld\n", ans, cnt);
		}
	}
	return 0;
}
