Seven Segment Graph

Problem

A seven segment display shows one digit by turning seven segments on and off. From here on, seven segment display is shortened to SSD.

The seven segments have the names and positions below. The DP segment for the decimal point is not used in this problem.

 AAAA
F    B
F    B
 GGGG
E    C
E    C
 DDDD

The segments meet at six endpoints. Call the top left, top right, middle left, middle right, bottom left and bottom right endpoints LT, RT, LM, RM, LB and RB. Each segment joins the two endpoints below.

Segment	Endpoints
A	LT, RT
B	RT, RM
C	RM, RB
D	LB, RB
E	LM, LB
F	LT, LM
G	LM, RM

An SSD lights the following segments to show the digits $0$ through $9$ .

$0$ : A, B, C, D, E, F
$1$ : B, C
$2$ : A, B, G, E, D
$3$ : A, B, C, D, G
$4$ : B, C, F, G
$5$ : A, C, D, F, G
$6$ : A, C, D, E, F, G
$7$ : A, B, C
$8$ : A, B, C, D, E, F, G
$9$ : A, B, C, D, F, G

The display of one digit can be read as a graph. Take the endpoints of the lit segments as nodes and the lit segments themselves as edges, and one graph comes out. Endpoints of segments that stay off are not nodes. The graph obtained this way is called the SSD graph of degree $0$ .

The SSD graph of degree $k$ ( $k > 0$ ) is built by splitting every edge of the degree $0$ SSD graph into $k+1$ edges and inserting $k$ new nodes in between. In the degree $1$ SSD graph, for example, one original edge turns into two edges with one new node between them.

You are given a graph with $n$ nodes and $m$ edges. Write a program that finds every SSD graph with the same shape as the given graph, that is, every SSD graph isomorphic to it, and reports its digit and degree.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 20$ ). The first line of each test case contains the number of nodes $n$ ( $1 \le n \le 500$ ) and the number of edges $m$ ( $1 \le m \le 1000$ ). Each of the next $m$ lines contains the numbers $u$ and $v$ of the two nodes an edge joins. Nodes are numbered from $1$ to $n$ . No edge is given twice, and no edge has $u$ equal to $v$ .

Output

For each test case, print Case X: Y on the first line, where $X$ is the test case number and $Y$ is the number of possible (digit, degree) pairs. On each of the next $Y$ lines, print one possible digit and degree separated by a space. Print them in increasing order of digit, and in increasing order of degree when the digit is the same. Print one blank line between test cases.