题目描述

肯努斯是“国际欧几里得奥林匹克竞赛”的组织者，他正在寻找一对整数，使用欧几里得算法需要很多步才能找到它们的最大公约数。

给定 $Q$ 个查询。第 $i$ 个查询表示为一对整数 $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$ 是一对唯一的整数，使得 $b=pa+q$ 且 $0 ≤ q < a$。那么，$(a,b)$ 的欧几里得步数是 $(q,a)$ 的欧几里得步数加 $1$。

约束条件

• $1 ≤ Q ≤ 3 × 10^5$
• $1 ≤ X_i,Y_i ≤ 10^{18}(1 ≤ i ≤ Q)$

输入

输入从标准输入读取，格式如下：

$Q$ $X_1$ $Y_1$ $:$ $X_Q$ $Y_Q$

输出

对于每个查询，打印最大的欧几里得步数，以及具有最大步数的整数对的个数，中间以空格分隔，对 $10^9+7$ 取模。

示例输入 1

3
4 4
6 10
12 11

示例输出 1

2 4
4 1
4 7

在第一个查询中，$(2,3)$、$(3,2)$、$(3,4)$ 和 $(4,3)$ 的欧几里得步数为 $2$。没有任何一对整数对的步数超过 $2$。

在第二个查询中，$(5,8)$ 的欧几里得步数为 $4$。

在第三个查询中，$(5,8)$、$(8,5)$、$(7,11)$、$(8,11)$、$(11,7)$、$(11,8)$ 和 $(12,7)$ 的欧几里得步数为 $4$。

示例输入 2

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

示例输出 2

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