题目描述

国際ユークリッドの互除法オリンピックの主催者であるけぬすくんは、 オリンピックをより面白くするため、$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$ で割ったあまりを空白区切りで出力せよ。

题目大意

定义 $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$ 取模.

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$ 回です。