[AGC015F] Kenus the Ancient Greek

定义 $F(x, y)$ 为执行 $gcd(x, y)$ 所需要的步数. $Q$ 次询问, 每次询问个给定 $X_i, Y_i$, 求满足 $1\leqslant x\leqslant X_i, 1\leqslant y\leqslant Y_i$ 的二元组的 $F(x,y)$ 的最大值和有多少个二元组的 $F(x, y)$ 达到了最大值, 答案对 $10^9 + 7$ 取模.

[problemUrl]: https://atcoder.jp/contests/agc015/tasks/agc015_f 国際ユークリッドの互除法オリンピックの主催者であるけぬすくんは、 オリンピックをより面白くするため、$ 2 $ 数のペアに対してユークリッドの互除法を走らせたとき、反復回数ができるだけ大きくなるようなペアを探しています。 $ Q $ 個のクエリが与えられます。$ i $ 個目のクエリは、$ 2 $ つの整数 $ X_i,Y_i $ で表され、 $ 1\ ≦\ x\ ≦\ X_i,\ 1\ ≦\ y\ ≦\ Y_i $ なるような $ (x,y) $ のペアの中での、ユークリッドの互除法の反復回数の最大値と、その最大値をとるペアの個数を $ 10^9+7 $ で割ったあまりを求めるクエリです。 全てのクエリに答えてください。ただし、ユークリッドの互除法の反復回数とは、任意の非負整数 $ a,b $ に対し、 - $ (a,b) $ と $ (b,a) $ の反復回数は等しい - $ (0,a) $ の反復回数は $ 0 $ - $ a\ >\ 0 $ かつ $ a\ ≦\ b $ なら、整数 $ p,q $ $ (0\ ≦\ q\ を用いて\ b $ を $ b=pa+q $ と一意的に表したとき、$ (q,a) $ の反復回数に $ 1 $ を加えた値が $ (a,b) $ の反復回数となる を満たすように定義されます。

入力は以下の形式で標準入力から与えられる。 > $ Q $ $ X_1 $ $ Y_1 $ $ : $ $ X_Q $ $ Y_Q $

各クエリに対し、ユークリッドの互除法の反復回数の最大値と、最大値を取るペアの個数を $ 10^9+7 $ で割ったあまりを空白区切りで出力せよ。

3
4 4
6 10
12 11

2 4
4 1
4 7

10
1 1
2 2
5 1000000000000000000
7 3
1 334334334334334334
23847657 23458792534
111111111 111111111
7 7
4 19
9 10

1 1
1 4
4 600000013
3 1
1 993994017
35 37447
38 2
3 6
3 9
4 2

### 制約 - $ 1\ ≦\ Q\ ≦\ 3\ ×\ 10^5 $ - $ 1\ ≦\ X_i,Y_i\ ≦\ 10^{18}(1\ ≦\ i\ ≦\ Q) $ ### Sample Explanation 1 $ 1 $ つ目のクエリでは、$ (2,3),(3,2),(3,4),(4,3) $ のユークリッドの互除法の反復回数が $ 2 $ 回です。$ 3 $ 回以上反復が必要な組はありません。 $ 2 $ つ目のクエリでは、$ (5,8) $ のユークリッドの互除法の反復回数が $ 4 $ 回です。 $ 3 $ つ目のクエリでは、$ (5,8),(8,5),(7,11),(8,11),(11,7),(11,8),(12,7) $ のユークリッドの互除法の反復回数が $ 4 $ 回です。