Clique

Cliquein an undirected graphis a subsetof vertices,two of whichare connectedby an edgeof the graph.In other words,it is a completesubgraphof the originalgraph.Cliquesizeis defined as thenumber of verticesin it.Your task- to determine thesize of the largestcliquein the graph.

Input

The firstline containsa single number -the number of testsT. This is followed bydescriptions ofTtests.Eachtest descriptionbeginswith the lineon which thetwo integersN (1 ≤ N ≤ 20) and M (0 ≤ M ≤ N(N-1)/2), where:

• N – numberof vertices,
• M – number of edges.

This is followed byM lines, i^thlinecontains a pairof numbers (s_i, f_i) – numberof verticesbetween whichthere is an edge (1 ≤ s_i, f_i ≤ N). All pairs (s_i, f_i) are different,one edgemay not bein the input datatwice.In thegraph has nomultiple edges(connectinganypair of verticesis at most oneedge).In thegraph has noelementarycycle(for each pair (s_i, f_i) is true, thats_i ≠ f_i).

Output

For each of theTtestoutputon a linesingle number - thesize of the largestcliqueof the graph.