Weird Coloring

You are given an undirected graph G. You should paint the edges of G with colors 0, 1, 2, ... such that:

1. Sum of colors of all edges be minimum.

2. For each edge with color 0, there must be an adjacent edge such that the color of that edge is 2. Two edges are adjacent if they have a common vertex.

Input

First line of Input contains the number of the tests.

For each case, first you are given 1 ≤ n ≤ 20 and 1 ≤ m ≤ 30, the number of vertices and edges respectively. In the following m lines, in each line you are given two endpoints of an edge.

Output

For each case, output minimum number of sum of the edges that have appropriate properties.

Examples