Dimensional Warp Drive

By the year 3133, space travel has become extremely common. With a dimensional warp drive you can move between two far-apart planets almost instantly.

The dimensional warp drive obeys the theory of Relativistic Curved Quantized Space (RCQS). According to this theory the universe has 11 dimensions, and each dimension is curved back onto itself: if you keep moving in one direction, you eventually return to your starting point.

The universe is also quantized, so along each dimension there are only 11 possible positions, numbered 0 through 10. Position 11 is the same as position 0, so every coordinate is taken modulo 11.

The first warp orbit was discovered in the year 3075. A warp orbit is described by 11 integer coordinates. Using a warp orbit once moves the ship from its current position to the position obtained by adding the orbit's coordinates to the current coordinates in each dimension (each taken modulo 11). Once discovered, a warp orbit may be reused any number of times from the year it was discovered onward.

Given a current position and a target position, write a program that finds the earliest year in which the target can be reached using only the warp orbits discovered so far. If the target can never be reached, print unreachable.

For example, suppose the current position is $(0,0,0,0,0,0,0,0,0,0,0)$ and the target position is $(0,0,3,0,0,3,0,0,3,0,0)$. If the orbit $(0,0,1,0,0,1,0,0,1,0,0)$ was discovered in 3075 and the orbit $(0,0,1,0,0,2,0,1,0,0,0)$ was discovered in 3082, then using the orbit discovered in 3075 three times reaches the target immediately.

The first line contains the number of test cases $T$. Each test case is given as follows.

• The first line contains the number of warp orbits $n$. ($n < 1000$)
• The second line contains the current starting position. Because the universe has 11 dimensions, the position consists of 11 integers, each between 0 and 10 inclusive.
• The third line contains the target position to reach. Each value is between 0 and 10 inclusive, and this position is always different from the starting position.
• Each of the next $n$ lines contains 12 integers. The first 11 are the coordinates of a warp orbit, and the last integer is the year that orbit was discovered. The year is between 3075 and 100000 inclusive.

For each test case, print on its own line the earliest year in which the target position can be reached using the warp orbits. If it can never be reached no matter how many years pass, print unreachable.