AtCoder Grand Contest 015 - Kenus the Ancient Greek

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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from math import gcd
import random, time

def gcdcount(n, m):
	(x, y) = (min(n, m), max(n, m))
	if x == 0:
		return 0
	else:
		return 1 + gcdcount(x, y % x)
fibo = [0, 1, 2]
for i in range(100):
	fibo.append(fibo[-1] + fibo[-2])
gcdfibo = [[], [(1, 2), (1, 3)]]
for i in range(2, 101):
	temp = []
	for (a, b) in gcdfibo[-1]:
		temp.append((b, a + b))
	(a, b) = (fibo[i], fibo[i + 2])
	temp.append((a, b))
	temp.sort()
	gcdfibo.append(temp)

def solve(x, y):
	if x > y:
		(x, y) = (y, x)
	mod = 10 ** 9 + 7
	if x == 1:
		return (1, y % mod)
	if (x, y) == (2, 2):
		return (1, 3)
	id = 1
	t = -1
	while True:
		if fibo[id + 1] <= x and fibo[id + 2] <= y:
			id += 1
		else:
			if fibo[id + 1] > x:
				if fibo[id + 2] > y:
					t = 0
				else:
					t = 1
			else:
				t = 2
			break
	if t == 0:
		res = 0
		for (a, b) in gcdfibo[id]:
			if a <= x and b <= y:
				res += 1
		return (id, res)
	elif t == 1:
		res = 0
		for (a, b) in gcdfibo[id]:
			if a <= x and (a, b) != (fibo[id], fibo[id + 2]) and (b <= y):
				res += (y - b) // a + 1
				res %= mod
		return (id, res)
	else:
		res = 0
		for (a, b) in gcdfibo[id + 1]:
			(u, v) = (b - a, a)
			if u <= x and v <= y:
				res += 1
				res %= mod
			if u <= y and v <= x:
				res += 1
				res %= mod
		return (id, res)
mod = 10 ** 9 + 7
Q = int(input())
start = time.time()
for _ in range(Q):
	(x, y) = map(int, input().split())
	(id, res) = solve(x, y)
	if (x, y) == (2, 2):
		res += 1
	print(id, res)


from math import gcd
q = int(input())
mod = 10 ** 9 + 7
tan = 100
tab = [[[0] * 2 for _ in range(tan)] for _ in range(tan)]
for _ in range(q):
	(x, y) = sorted(map(int, input().split()))
	ma = 0
	(i, j) = (1, 1)
	while j <= x and i + j <= y:
		(i, j) = (j, i + j)
		ma += 1
	if x == 1 or y <= 2:
		print(1, x * y % mod)
	else:
		ans = 0
		if x >= i:
			ans += max(0, (y - j) // i + 1)
		if y >= i:
			ans += max(0, (x - j) // i + 1)
		(i, j) = (1, 1)
		for c in range(ma - 1):
			(k, l) = (j, i + j * 2)
			for _ in range(ma - c - 1):
				(k, l) = (l, k + l)
			if x >= k:
				ans += max(0, (y - l) // k + 1)
			if y >= k:
				ans += max(0, (x - l) // k + 1)
			(i, j) = (j, i + j)
		print(ma, ans % mod)


m = 10 ** 9 + 7
f = max
r = range
for _ in r(int(input())):
	(x, y) = sorted(map(int, input().split()))
	s = -1
	i = j = 1
	while j <= x and i + j <= y:
		(i, j, s) = (j, i + j, s + 1)
	if x < 2 or y < 3:
		print(1, x * y % m)
		continue
	a = f(0, (y - j) // i + 1) + f(0, (x - j) // i + 1)
	i = j = 1
	for c in r(s):
		(k, l) = (j, i + j * 2)
		for _ in r(s - c):
			(k, l) = (l, k + l)
		if x >= k:
			a += f(0, (y - l) // k + 1)
		if y >= k:
			a += f(0, (x - l) // k + 1)
		(i, j) = (j, i + j)
	print(s + 1, a % m)


q = int(input())
mod = 10 ** 9 + 7
for _ in range(q):
	(x, y) = sorted(map(int, input().split()))
	ma = 0
	(i, j) = (1, 1)
	while j <= x and i + j <= y:
		(i, j) = (j, i + j)
		ma += 1
	if x == 1 or y <= 2:
		print(1, x * y % mod)
	else:
		ans = 0
		if x >= i:
			ans += max(0, (y - j) // i + 1)
		if y >= i:
			ans += max(0, (x - j) // i + 1)
		(i, j) = (1, 1)
		for c in range(ma - 1):
			(k, l) = (j, i + j * 2)
			for _ in range(ma - c - 1):
				(k, l) = (l, k + l)
			if x >= k:
				ans += max(0, (y - l) // k + 1)
			if y >= k:
				ans += max(0, (x - l) // k + 1)
			(i, j) = (j, i + j)
		print(ma, ans % mod)


q = int(input())
m = 10 ** 9 + 7
for _ in range(q):
	(x, y) = sorted(map(int, input().split()))
	s = 0
	i = j = 1
	while j <= x and i + j <= y:
		(i, j) = (j, i + j)
		s += 1
	if x == 1 or y <= 2:
		print(1, x * y % m)
	else:
		a = 0
		a += max(0, (y - j) // i + 1)
		a += max(0, (x - j) // i + 1)
		i = j = 1
		for c in range(s - 1):
			(k, l) = (j, i + j * 2)
			for _ in range(s - c - 1):
				(k, l) = (l, k + l)
			if x >= k:
				a += max(0, (y - l) // k + 1)
			if y >= k:
				a += max(0, (x - l) // k + 1)
			(i, j) = (j, i + j)
		print(s, a % m)