题目描述

国际欧几里得辗转相除法奥林匹克的主办者けぬす君为了让奥林匹克更加有趣，正在寻找一对使欧几里得辗转相除法迭代次数尽可能大的整数对。

现有 $Q$ 个查询。第 $i$ 个查询由两个整数 $X_i, Y_i$ 给出，询问满足 $1 \leq x \leq X_i$，$1 \leq y \leq Y_i$ 的所有 $(x, y)$ 的欧几里得辗转相除法迭代次数的最大值，以及能达到该最大迭代次数的整数对的个数，答案对 $10^9+7$ 取模。

请回答所有查询。欧几里得辗转相除法的迭代次数定义如下，对于任意非负整数 $a,b$：

• $(a, b)$ 和 $(b, a)$ 的迭代次数相同。
• $(0, a)$ 的迭代次数为 $0$。
• 若 $a>0$ 且 $a \leq b$，且能表示 $b = pa+q$（$0 \leq q < a$ 的整数 $p, q$），则 $(a, b)$ 的迭代次数为 $(q, a)$ 的迭代次数加 $1$。

输入格式

输入由以下形式组成，从标准输入读入：

$Q$
$X_1\ Y_1$
$X_2\ Y_2$
$\vdots$
$X_Q\ Y_Q$

输出格式

对于每个查询，输出一行，用空格隔开两个整数，分别表示欧几里得辗转相除法的最大迭代次数，以及能达到该最大迭代次数的整数对的个数，对 $10^9+7$ 取模。

样例 1

输入

3
4 4
6 10
12 11

输出

2 4
4 1
4 7

样例 2

输入

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 \leq Q \leq 3 \times 10^5$
• $1 \leq X\_i, Y\_i \leq 10^{18} \quad (1 \leq i \leq Q)$

样例解释 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$。

由 ChatGPT 5 翻译