#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;
#define iter(i, n) for (int i = 1; i <= n; ++i)
const int mod = 1e9 + 7;
typedef long long i64;
typedef pair<i64, i64> pii;
#define fi first
#define se second
vector<pii> vec[100];
i64 f[100];
int F(i64 a, i64 b) {
if (a < b) swap(a, b);
return !b ? 0 : F(b, a % b) + 1;
}
int main() {
f[0] = 1, f[1] = 1;
int n = 1;
while (f[n] <= 1e18) {
++n;
f[n] = f[n - 1] + f[n - 2];
}
f[n + 1] = f[n];
--n;
vec[0].push_back(pii(0, 1));
vec[0].push_back(pii(0, 2));
iter(i, n) {
for (pii p : vec[i - 1]) {
i64 a = p.fi, b = p.se;
// if (i == 4) printf("[%lld %lld] %d %d %lld\n", a, b, i-1, F(a, b), f[i+1]);
assert(F(a, b) == i - 1);
// printf("%d [%lld %lld]", i, a, b);
for (; a + b <= f[i + 2]; a += b) {
//gcd(f[i+2],f
if (F(b, a + b) == i) vec[i].push_back(pii(b, a + b));
}
}
}
int q;
scanf("%d", &q);
iter(id, q) {
i64 a, b;
scanf("%lld%lld", &a, &b);
if (a > b) swap(a, b);
int ans = 1; i64 cnt = 0;
iter(i, n) {
if (a >= f[i] && b >= f[i + 1]) ans = i;
else break;
}
printf("%d ", ans);
for (pii p : vec[ans - 1]) {
if (p.se <= a && p.fi + p.se <= b && p.fi != p.se) cnt = (cnt + (b - p.fi) / p.se) % mod;
swap(a, b);
if (p.se <= a && p.fi + p.se <= b && p.fi != p.se) cnt = (cnt + (b - p.fi) / p.se) % mod;
swap(a, b);
}
printf("%lld\n", ans != 1 ? cnt : a * b % mod);
}
//
return 0;
}