Score : 1700 points
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:
The input is given from Standard Input in the following format:
Q X_1 Y_1 : X_Q Y_Q
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.
3 4 4 6 10 12 11
2 4 4 1 4 7
In the first query, (2,3), (3,2), (3,4) and (4,3) have a Euclidean step count of 2. No pairs have a step count of more than 2.
In the second query, (5,8) has a Euclidean step count of 4.
In the third query, (5,8), (8,5), (7,11), (8,11), (11,7), (11,8), (12,7) have a Euclidean step count of 4.
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