Bracelet

Time Limit: 1 Second    Memory Limit: 32768 KB

The One visited Adventure Island and got a precious bracelet from the locals. Unfortunately the thread broke and the pieces got all around. He is not quite sure whether he has lost any of them. And he wants you to tell him whether the remaining pieces can restore a bracelet.

The shape of the pieces are shown in figure(a). A1, A2, A3 are three joints. Pieces are connected as in figure(b). Only matched joints can be connected.

 A2 2 ... 2 5 ... 5
 / / \ / \
 A1 ... ... 1 ... ... 4 ... 4 ... ... 7 ...
 \ \ / \ /
 A3 3 ... 3 6 ... 6
 figure(a) figure(b)


 2 ... 2 5 ... 5
 / \ / \
 1 ... ... 4 4 ... ... 7
 \ / \ /
 3 ... 3 6 .X. 8
 can be connected can not be connected
 figure(c)

Input

There are multiple tests. The first line contains the total number of tests. There is a blank line preceding each test.

Each test start with two integers N - the number of type of pieces and C - the number of different joints. The following N lines contain information about each piece, Ai1, Ai2, Ai3 - the three joints of the piece and Ti - the number of this type. (N <= 15, total Ti <= 20, and 1 <= C <= N*3)

Output

Each test begins with "Case #i"

If a bracelet can be restored, output "^_^", print "~~~><~~~" otherwise.

Separate each test with a blank line.

Sample Input

2

1 1
1 1 1 10

2 2
1 1 1 1
1 1 2 1

Sample Output

Case #1
^_^

Case #2
~~~><~~~

Submit

Source: ZOJ Monthly, March 2003