Mad Veterinarian

Mad Veterinarian puzzles feature a mad veterinarian who has built several machines, each of which transforms one animal into one or more animals — and each machine can also be run in reverse. The challenge is to decide whether one collection of animals can be turned into another by applying the machines in some order, forward or reversed. For example:

• Machine A turns one ant into one beaver.
• Machine B turns one beaver into one ant, one beaver, and one cougar.
• Machine C turns one cougar into one ant and one beaver.

Can we turn a beaver and a cougar into 3 ants? Yes: {b, c} → (apply C) → {a, 2b} → (apply A in reverse) → {2a, b} → (apply A in reverse) → {3a}. That takes 3 steps.

Can we turn one ant into 2 ants? No.

Every such puzzle has these properties:

1. In forward mode, each machine turns one animal of a given species into a finite, non-empty collection of animals from the puzzle's species.
2. Each machine can also be run in reverse.
3. There is exactly one machine per species, and in forward mode that machine takes one animal of that species as input.

For this problem every puzzle has exactly three machines, A, B, and C, acting on species a, b, and c respectively. Your task is to find the length of the shortest sequence of machine applications (if any) that turns the starting collection into the target collection.

The first line contains an integer P (1 ≤ P ≤ 1000), the number of data sets that follow. The data sets are processed identically and independently.

Each data set begins with a line containing an integer N, the number of puzzle questions in that data set. The next three lines describe machines A, B, and C in that order. Each machine line has three integers separated by spaces, giving how many animals of species a, b, and c the machine outputs for its single input animal. The following N lines each contain six integers separated by single spaces: the starting counts of animals a, b, and c, followed by the desired ending counts of animals a, b, and c.

For each puzzle question, output one line. If the target collection cannot be reached from the starting collection, output NO SOLUTION. Otherwise output a single integer: the minimum number of machine applications needed to reach the target, where every forward or reverse application counts as one step.