You are given an undirected graph \textbf{G}. You should paint the edges of \textbf{G} with colors \textbf{0}, \textbf{1}, \textbf{2}, ... such that: \begin{enumerate} \item Sum of colors of all edges be minimum. \item For each edge with color \textbf{0}, there must be an adjacent edge such that the color of that edge is \textbf{2}. Two edges are adjacent if they have a common vertex. \end{enumerate} \InputFile First line of Input contains the number of the tests. For each case, first you are given \textbf{1} ≤ \textbf{n} ≤ \textbf{20} and \textbf{1} ≤ \textbf{m} ≤ \textbf{30}, the number of vertices and edges respectively. In the following \textbf{m} lines, in each line you are given two endpoints of an edge. \OutputFile For each case, output minimum number of sum of the edges that have appropriate properties.