Problem Description

Assume there are two jugs, $A$ and $B$, with an unlimited water supply. There are three ways to manipulate the water:
- Fill one jug with water.
- Empty one jug.
- Pour water from one jug into the other.

When pouring water from one jug to another, the pouring stops if the first jug is empty or the second jug is full. For example, if jug $A$ holds 5 gallons and jug $B$ holds 6 gallons, and there is a total of 8 gallons, pouring from jug $A$ to jug $B$ would fill jug $B$ to its capacity, leaving 3 gallons in jug $A$.

The problem is defined by three parameters: $C_a$, $C_b$, and $N$, representing the capacities of jugs $A$ and $B$, and the target amount of water $N$ respectively. The goal is to provide a sequence of steps to make the amount of water in jug $B$ exactly $N$.

Input Format

The first line contains the number of test cases $T$.

The next $T$ lines each contain three numbers $C_a$, $C_b$, and $N$, as described in the problem.

$T$ does not exceed 30, $0 < C_a ≤ C_b$, $N ≤ C_b ≤ 1000$, and $C_a$ and $C_b$ are coprime.

Output Format

The output consists of $T$ lines. The first number on each line is the number of steps $a_i$ required to achieve the goal (the problem guarantees a solution exists).

Following $a_i$ are the numbers representing the operations:
- 1: $fill A$ (fill jug $A$ to its capacity)
- 2: $fill B$
- 3: $empty A$ (empty jug $A$)
- 4: $empty B$
- 5: $pour B A$ (pour from jug $B$ to jug $A$ until jug $A$ is full or jug $B$ is empty)
- 6: $pour A B$

Sample Input and Output

Sample Input #1

2
3 5 4 
5 7 3 

Sample Output #1

6 2 5 3 5 2 5 
6 1 6 1 6 4 6 

Sample Input #2

1
26 29 11

Sample Output #2

22 1 6 1 6 4 6 1 6 4 6 1 6 4 6 1 6 4 6 1 6 4 6 

Notes

A special judge (spj) is enabled.

If your solution is better than the provided answer, you will receive a notification (UKE). In such cases, please contact the administrator to update the data.

If your solution is worse than the provided answer, your score will be reduced accordingly.

见题面 Input 部分

见题面 Output 部分