Statement

There are two allowed edit operations on positive integers: reshuffle and resize.

A reshuffle rearranges the order of digits arbitrarily. For the purpose of a reshuffle we will assume that each number can start with arbitrarily many leading zeros and those can be rearranged as well. For example, you may reshuffle \(104\) to \(40\,010\), \(40\,010\) back to \(104\), \(11\,234\) to \(41\,213\), or \(1\) to a googol (\(10^{100}\)).

A resize modifies the value of number. The width of a resize is the absolute difference between the original and the new number. E.g., a resize of width 3 can change 158 into either 155 or 161.

Reshuffles are completely free.

Given a sequence of edits, the length of that sequence is the number of resizes, the width of the sequence is the maximum width of a resize used (or zero if there are no resizes), and the area of the sequence is the product of its length and width.

Given positive integers \(a\) and \(b\), find the minimum area of an edit sequence that changes \(a\) to \(b\), and construct one such sequence.

Input format

The first line of each input file contains the number \(t\) of test cases.

Each of the following \(t\) lines contains two positive integers \(a\) and \(b\).

Output format

Subtask M4 has a special output format, the difference is explained below.

For each test case output three lines:

• One line with the minimum area \(x\) of an edit sequence that transforms \(a\) into \(b\).
• One line with one non-negative integer \(y\): the number of editing steps in your chosen optimal edit sequence.
• One line with a sequence of \(y+1\) positive integers \(s_0, s_1, \dots, s_y\) that represents your chosen optimal sequence of edits.

More precisely, your output must satisfy the following constraints:

• \(s_0 = a\)
• \(s_y = b\)
• each of the intermediate \(s_i\) is a positive integer with at most 50 digits
• if we interpret the sequence \(s\) as \(y\) consecutive edits (each being a reshuffle if it can and a resize if it cannot), the area of this sequence must be exactly \(x\)
• \(0\leq y\leq 500\)
• Note that \(y\) is the number of steps taken during editing. This is not the length of that sequence of edits in the specific sense defined above, as some of those edits can be reshuffles.
• Also note that we do not care about minimizing \(y\). Within the given constraints \(y\) may be arbitrary.

It is guaranteed that for each test case in subproblems M1-M3 there is always an optimal sequence of edits that can be output in the above format.

(Also, for these tests the bounds “at most 50 digits” and “\(y\leq 500\)” should both be reasonably loose to not affect valid solutions.)

Partial scores

In each of the subproblems M1-M3, 50% of points will be awarded for an output file which is not completely correct but satisfies the following criteria:

• contains exactly 3 lines of output per test case
• in each test case the value \(x\) (minimum area) is correct

Subproblem M1 (18 points, public)

Input file: M1.in

Constraints: \(t=100\) and in each test \(1 \leq a,b < 10^5\).

Subproblem M2 (57 points, secret)

Input file: M2.in

Constraints: \(t=100\) and in each test \(1 \leq a,b < 10^{16}\).

Subproblem M3 (13 points, secret)

Input file: M3.in

Constraints: \(t=100\) and in each test \(1 \leq a,b < 10^{25}\).

Subproblem M4 (12 points, secret)

Input file: M4.in

Constraints: \(t=100\) and in each test \(1 \leq a,b < 10^{1000}\).

In this subproblem only output one line per test case with the optimal value \(x\).

(The full output file with constructed solutions would be too large to submit.)

For this subtask there is no partial score.

Example

2
47 47
4200 7017

0
0
47
6
5
4200 420 417 174 7014 7017

The sample solution to the second test case contains two resizes: in the second step we decrease the number by 3 and in the last step we increase it by 3. Thus, the width of this solution is \(\max(3,3) = 3\), its length is 2, and therefore its area is \(3\times 2 = 6\).

Note that the number of reshuffles does not matter. In particular, in the sequence shown above the reshuffle \(417\to 174\) can easily be omitted and the solution would still be valid.