q1

Let's consider a square matrix of size N?×?N, where N = R -­­­­­­­­­­­ L + 1. We will enumerate the columns of this matrix with consecutive integers from L to R (the leftmost column will be assigned number L and the rightmost - number R). In similar manner we will enumerate rows with the same integers (the top row will be assigned number L and the bottom row - number R).

Every cell of this matrix has an integer written inside it. The cell at the intersection of row X and column Y has integer (X xor Y) written inside.

Two cells are called adjacent if and only if they have a common side. That way every inner cell have 4 neighbors and any of four corner cells have 2 neighbors.

A walk is a sequence of cells C₀, C₁, C₂, ..., C_K, where for every 1 = i = K the cells C_i-1 and C_i are adjacent and for every 0 = j = K the number written inside cell C_j is equal j. The number K is the length of that walk.

Your task is for given L and R values, find the maximal possible value of K, as well as the count C of different walks with that maximal length. As the value of C could be very large, output it modulo (10⁹ + 7).

Input

The first line of the input contains an integer T denoting the number of test cases.
The description of T test cases follows.
For each test case, the only line of input contains two integers L and R.

Output

For each test case, output a single line containing two integers K and C.
The value of C should be printed modulo (10⁹ + 7).

Constraints

• 1 = T = 20 000
• 1 = L = R = 10¹⁸

Subtasks

• Subtask #1: 1 = T = 500; 0 = R - L = 300 (8 points)
• Subtask #2: original constraints, only the value of K will be checked. (24 points)
• Subtask #3: original constraints (68 points)

Example

Input: 4 1 1 1 2 1 3 2 3 Output: 0 1 0 2 3 4 1 4

 

Explanation

Example case 1. The matrix contains just one cell, so, there is no possibility to make a single move, thus K = 0. We have just one possibility - to start the walk at the only cell and to end it immediately.

Example case 2. The matrix doesn't contains a cell with number one inside, so, there once again is no possibility to make a single move, thus K = 0. Our walk is just a single cell with number zero inside and there are two such cells, thus C = 2. The matrix in this case looks like this:

(1 xor 1) (1 xor 2) = 0 3 (2 xor 1) (2 xor 2) = 3 0

Example case 3. The four possible walks are:

0 3 2 0 3 2 0 3 2 0 3 2 3 0 1 3 0 1 3 0 1 3 0 1 2 1 0 2 1 0 2 1 0 2 1 0

Example case 4. The four possible walks are:

0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 q2

Devu likes to play with a lock of N dials. Each dial rotates from numbers 0 to 9 clockwise (i.e. 0 to 1, 2 to 3 and 8 to 9). You can not rotate from 9 to 0.

Initially all the dials of the lock are set to 0. From the current lock, Devu can move any dial to at most 10 different positions (i.e. 0 to 9), so there are total 10^N different locks possible.

Let us say for a lock we define cost of converting the initial lock (all zeros) to this lock. For this, we have to rotate each dial to corresponding position in the lock. Cost of moving a single dial to value x takes x seconds.
eg. cost of moving to 123 is 1 + 2 + 3 = 6 and cost of moving to 99 is 9 + 9 is 18.

Now Devu has to hurry up to meet his girlfriend, So he has at most M seconds to spend, he wonders how many possible locks he can create such that when a lock is represented as a decimal number, it should be divisible by P. As answer could be large, print answer modulo 998244353.

Input

Only line of input will contain three integers N, P, MM respectively. Use of MM is defined in the output section.

Output

Print a single line containing MM + 1 integers, i^th (0 based indexing) of them should represent the
answer for the problem with given N, P and M = i.

Constraints

• Subtask #1: (10 points) 1 = N = 1000, 1 = P = 50, 1 = MM = 50 TL : 5 secs
• Subtask #2: (20 points) 1 = N = 10^9, 1 = P = 50, 1 = MM = 50 TL : 5 secs
• Subtask #3: (30 points) 1 = N = 10^9, 1 = P = 50, 1 = MM = 500 TL : 10 secs
• Subtask #4: (40 points) 1 = N = 10^9, 1 = P = 16, 1 = MM = 15000 TL : 15 secs

Example

Input: 2 3 3 Output: 1 1 1 5 Input: 2 4 4 Output: 1 1 2 3 5

Explanation

Example #1.
For M = 0, we can have only one lock, ie. all zeros 00, it is divisible by 3.
For M = 1, we can have only one lock, ie. all zeros 00, it is divisible by 3.
For M = 2, we can have only one lock, ie. all zeros 00, it is divisible by 3.
For M = 3, we can have 5 locks whose decimal representation is divisible by 3. They are 00, 03, 21, 30 and 12.

Example #2.
For M = 0, we can have only one lock, ie. all zeros 00, it is divisible by 4.
For M = 1, we can have only one lock, ie. all zeros 00, it is divisible by 4.
For M = 2, we can have 2 locks whose decimal representation is divisible by 4. They are 00 and 20.
For M = 3, we can have 3 locks whose decimal representation is divisible by 4. They are 00, 12 and 20.
For M = 4, we can have 5 locks whose decimal representation is divisible by 4. They are 00, 04, 12, 20 and 40.