For the fourth time this month only, the absent minded
mathematics professor Bolkás had lost his keys. Realizing, that
a change of personality to one that keeps track of trivialities
seemed unlikely, he started to invent a lock with a
non-material key. Of course, he could just have chosen a
combination lock, but as there were far too many numbers flying
around in his daily thoughts, this idea was indeed a poor one.
What he needed, was a lock which could be deactivated by
solving a mathematical problem. For this type of lock, he could
always be certain to have the “key” on him. However, for the
sake of safety, the problem had to be hard enough for anyone
trying to find the solution merely by testing all
possibilities. Still, if you knew the mathematics behind the
lock, you should be able to deactivate it.
Being a big fan of modular arithmetic, Bolkás designed the
lock as a
array of four modular devices (cf. fig. 1). A modular
device is a discrete counter with a display showing the current
state of the counter, and a trigger. Each counter can be in any
of the states , where is the period of the counter. By trigging a counter,
the state of the counter changes from to , except when the state is
, in which case the
new state is . For each
row and each column of the array, the professor put an
increaser button on the panel of the lock. By pushing the
increaser button for a row or column, both counters in that row
or column are trigged. The lock is deactivated exactly when all
four modular devices are in state . Bolkás also added a mechanism to
activate the lock. Upon locking, each modular device is put in
a randomly chosen state, not all equal to (since in that case the lock would
be immediately deactivated). Sadly enough, the professor soon
found that for some quadruples of periods, it sometimes
happened that the lock was put in a combination of states such
that it could not be deactivated! However, it did not take him
long to find an interesting relation between the locks, which
helped him, and hopefully you, to decide if a lock could be
deactivated or not: He observed that a lock whose modular
devices had the periods , , and , and were put in the states
, , and , could be deactivated if
and only if a lock with all modular devices having the
same period and the states , could. The
function
is the greatest common divisor of , , , and .
Input
The first line of input consists of a single positive
integer .
Thereafter scenarios
follow. Each scenario consists of two rows of four integers
each. Row of each
scenario, , contains the four integers , , , and , in that order. and are the current state and
period respectively, of the modular device at row and column . No period is larger than , and .
Output
For each scenario, output one line containing the text
“Yes” if it is possible to deactivate
the lock by pressing the four row and column increaser buttons
in some order. Otherwise the test “No” should be printed.
Sample Input 1 |
Sample Output 1 |
2
0 11 17 13
5 8 6 11
1 1 3 3
1 0 3 3
|
Yes
No
|