Problem C: Pour (2011-ish)

You are out exploring Elora Gorge. You discover a cave. Foolishly, you enter the cave to explore.

In the cave, you find a beautiful fountain pouring into a pool. Two pitchers are in front of the pool. One is marked as seven litre capacity, the other as five litre capacity.

All of a sudden, the entrance to the cave closes! A disembodied voice booms out, “Fill one of the pitchers with precisely one litre of water. Do so, and I will let you leave. Fail, and be trapped forever!”

You manage to subdue your panic, to keep a level head. You realize there is a sequence of “moves” — filling the first pitcher or the second pitcher completely from the fountain, emptying completely either pitcher into the pool, and pouring as much as possible from the first pitcher into the second (thereby either emptying the first pitcher or completely filling the second) or vice versa — that can leave exactly one litre of water in one of the two pitchers. You quickly sketch out a solution, follow it, and are released to your freedom!

Input

The input commences with an integer t that states the number of trials (0 < t ≤ 100). A line with three integers follows for each trial: X, the capacity of the first pitcher; Y, the capacity of the second pitcher; and Z, the target amount you are to leave in one pitcher or the other; 0 < X ≤ 100, 0 < Y ≤ 100, and 0 < Z ≤ max(X, Y).

The permitted moves in a solution are

1. Fill the first pitcher.
2. Fill the second pitcher.
3. Empty the first pitcher.
4. Empty the second pitcher.
5. Pour as much as possible from the first pitcher into the second (not spilling anything).
6. Pour as much as possible from the second pitcher into the first (not spilling anything).

Sample Input

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

Output

For each trial, write the shortest canonical solution out. Assume the first and second pitchers start out empty: <0, 0>. (Do not print this starting state.) Print the state of the two pitchers, <amount in first, amount in second>, per line after each move. If there is no solution for the trial, print “no solution”.

By shortest solution, we mean a solution with the fewest steps. Of course, there may more than one shortest solution; so print out the shortest canonical solution.

A solution is canonical in this case if there is no other solution of the same length that comes before it lexicographically by move choices — a: Fill the first pitcher; b: Fill the second pitcher; ... — as listed above. For example, if we have two solutions, aeae and bfcf, the second one is not canonical because aeae < bfcf by dictionary order. And aeae is canonical as long as no four-move solution comes before it lexicographically.

Sample Output

5 0
3 2

no solution

5 0
0 5
5 5
4 6
4 0
0 4
5 4
3 6

7 0
2 5
2 0
0 2
7 2
4 5
4 0
0 4
7 4
6 5

5 0
0 5
5 5
3 7
3 0
0 3
5 3
1 7