#include <bits/stdc++.h>

#define int long long

const int N = 100, lim = 89;
const int P = 1e9 + 7;

struct Node {
  int x, y;
};

std::vector<Node> vec[N];
int fib[N];

inline void init() {
  fib[0] = fib[1] = 1;
  for (int i = 2; i <= lim + 1; ++i)
    fib[i] = fib[i - 1] + fib[i - 2];

  vec[1].push_back({ 1, 2 });
  vec[1].push_back({ 1, 3 });
  vec[1].push_back({ 1, 4 });

  for (int i = 2; i <= lim; ++i) {
    // cerr << i << endl;
    for (auto a : vec[i - 1]) {
      int y = a.y, x = a.x + y;
      while (x <= fib[i + 2] + fib[i - 1] && y <= fib[i + 2] + fib[i - 1]) {
        vec[i].push_back({ y, x });
        x += y;
      }
    }
  }

  /*
  for (int i = 1; i <= 10; ++i) {
    cerr << i << " : ";
    for (auto a : vec[i]) {
      printf("(%lld, %lld) ", a.x, a.y);
    }
    cerr << endl;
  }
  */

}

inline void solve(int n, int m) {

  if (n == 1) {
    printf("1 %lld\n", m % P);
    return;
  }
  if (n == 2 && m == 2) {
    puts("1 4");
    return;
  }

  int ans = 0;
  for (int i = 1; i <= lim; ++i) {
    if (fib[i] <= n && fib[i + 1] <= m) {
      ans = i;
    } else {
      break;
    }
  }

  int cnt = 0;

  for (auto w : vec[ans - 1]) {
    int x = w.x, y = w.y;
    // cerr << x << " " << y << endl;
    if (y <= m)
      cnt = (cnt + (n - x) / y) % P;
    if (y <= n)
      cnt = (cnt + (m - x) / y) % P;
  }

  printf("%lld %lld\n", ans, (cnt % P + P) % P);

}

signed main() {
  // freopen("data", "r", stdin);
  // freopen("1.out", "w", stdout);
  init();
  int q; std::cin >> q;
  while (q--) {
    int x, y; scanf("%lld %lld", &x, &y);
    if (x > y) std::swap(x, y);
    solve(x, y);
  }
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>

#define int long long

const int N = 100, lim = 89;
const int P = 1e9 + 7;

struct Node {
  int x, y;
};

std::vector<Node> vec[N];
int fib[N];

inline void init() {
  fib[0] = fib[1] = 1;
  for (int i = 2; i <= lim + 1; ++i)
    fib[i] = fib[i - 1] + fib[i - 2];

  vec[1].push_back({ 1, 2 });
  vec[1].push_back({ 1, 3 });
  vec[1].push_back({ 1, 4 });

  for (int i = 2; i <= lim; ++i) {
    // cerr << i << endl;
    for (auto a : vec[i - 1]) {
      int y = a.y, x = a.x + y;
      while (x <= fib[i + 2] + fib[i - 1] && y <= fib[i + 2] + fib[i - 1]) {
        vec[i].push_back({ y, x });
        x += y;
      }
    }
  }

  /*
  for (int i = 1; i <= 10; ++i) {
    cerr << i << " : ";
    for (auto a : vec[i]) {
      printf("(%lld, %lld) ", a.x, a.y);
    }
    cerr << endl;
  }
  */

}

inline void solve(int n, int m) {

  if (n == 1) {
    printf("1 %lld\n", m % P);
    return;
  }
  if (n == 2 && m == 2) {
    puts("1 4");
    return;
  }

  int ans = 0;
  for (int i = 1; i <= lim; ++i) {
    if (fib[i] <= n && fib[i + 1] <= m) {
      ans = i;
    } else {
      break;
    }
  }

  int cnt = 0;

  for (auto w : vec[ans - 1]) {
    int x = w.x, y = w.y;
    // cerr << x << " " << y << endl;
    if (y <= m)
      cnt = (cnt + (n - x) / y) % P;
    if (y <= n)
      cnt = (cnt + (m - x) / y) % P;
  }

  printf("%lld %lld\n", ans, (cnt % P + P) % P);

}

signed main() {
  // freopen("data", "r", stdin);
  // freopen("1.out", "w", stdout);
  init();
  int q; std::cin >> q;
  while (q--) {
    int x, y; scanf("%lld %lld", &x, &y);
    if (x > y) std::swap(x, y);
    solve(x, y);
  }
  return 0;
}

```