Chef Shifu wanted to celebrate the success of his new restaurant with all his employees. He was willing to host a party and he had decided the location of the party as well. However, Chef Shifu was a shy person and wanted to communicate with the least possible employees to inform them about the party, and that these employees could inform their friends.

Note that an employee could only inform his/her immediate friends about the party, not his/her friends’ friends.

Chef Shifu has a list of all the friendships among his employees. Help him find the minimum number of employees he should inform, so that every employee knows about the celebration party.

-----Input-----
First line contains a single integer T - the total number of testcases.

T testcases follow. For each testcase:

The first line contains 2 space-separated integers N and M - the total number of employees working under Chef Shifu and the number of friendship relations.

M lines follow - each line contains 2 space-separated integers u and v, indicating that employee u is a friend of employee v and vice-versa.

The employees are numbered from 1 to N, and each employee is assigned a distinct integer.



-----Output-----
For each testcase, print the minimum number of employees to be informed on a new line.

-----Constraints-----
Subtask 1: 5 points

1 ≤ T ≤ 5

1 ≤ N ≤ 4

0 ≤ M ≤ N*(N-1)/2



Subtask 2: 35 points

1 ≤ T ≤ 5

1 ≤ N ≤ 15

0 ≤ M ≤ N*(N-1)/2



Subtask 3: 60 points

1 ≤ T ≤ 5

1 ≤ N ≤ 20

0 ≤ M ≤ N*(N-1)/2


-----Example-----
Input
2
3 3
1 2
2 3
1 3
4 3
1 2
2 3
3 4

Output
1
2

Explanation

In testcase 1, since every employee is a friend of every other employee, we just need to select 1 employee.
In testcase 2, selecting employees 2 and 4 would ensure that all 4 employees are represented.

Similarly, selecting employees 1 and 3 would also ensure that all 4 employees are selected.

In both cases, we must select 2 employees in the best case.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 't=int(input())\nfor _ in range(t):\n    n,m=map(int,input().split())\n    mat=[0 for i in range(n)]\n    #mat=[[0 for i in range(n)] for j in range(n)]\n    for i in range(m):\n     u,v=map(int,input().split())\n     u,v=(u-1),(v-1)\n     mat[u]|=(1<<v)\n     mat[v]|=(1<<u)\n    for i in range(n):\n     mat[i]|=(1<<i)    \n \n    goal=(2**n)-1\n    ans=n\n\n    for i in range(1,goal+1):\n     mvs=0\n     loc=0\n     for j in range(n):\n      if(i&(1<<j)):\n       loc|=mat[j]\n       mvs+=1\n     if(loc==goal):\n      ans=min(mvs,ans)\n    print(ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13397