One day your university decided to run some statistics. They wanted to study friendship relations among boys and girls, and its effectiveness on their grades.
Strange thing about your university is that it has the exact same number of boys and girls. More formally, the university has P boys numbered from 1 to P, and P girls numbered from 1 to P.
We know that any pair of boys are surely friends, and any pair of girls are definitely friends. However, boys and girls are not always friends. To be precise, the university has a list of length N containing the friendship relations between girls and boys. the ith friendship relation is described by two integers bi and gi meaning that the boy number bi and girl number gi are friends.
One of the statistics your university is interested in, is the largest group of people (boys and girls) where any pair of them are friends. Can you write a program that would solve such a problem?
The first line contains an integer T, the number of test cases.
Each test case starts with a line containing 2 space separated integers P and N denoting both the number of boys and girls at your university, and the number of friendship relations. (1 ≤ P ≤ 20), (0 ≤ N ≤ P2).
N lines follow. The ith line of them contains 2 space separated integers bi, gi describing a friendship relation.
For each test case print a single line, containing a single integer, denoting the number of people in the largest group where any pair of people among them are friends.
## Input
The first line contains an integer T, the number of test cases.Each test case starts with a line containing 2 space separated integers P and N denoting both the number of boys and girls at your university, and the number of friendship relations. (1 ≤ P ≤ 20), (0 ≤ N ≤ P2).N lines follow. The ith line of them contains 2 space separated integers bi, gi describing a friendship relation.
## Output
For each test case print a single line, containing a single integer, denoting the number of people in the largest group where any pair of people among them are friends.
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of guns.
Let $ W \in \mathbb{R}^+ $ be the initial weight of Simon.
Let $ G = \{(c_i, r_i) \mid i \in \{1, \dots, N\}\} $ be the set of guns, where:
- $ c_i \in \mathbb{Z}^+ $ is the cost per unit weight of gun $ i $,
- $ r_i \in [0, 1] $ is the minify ratio of gun $ i $ (weight becomes $ r_i \cdot \text{current weight} $).
**Constraints**
1. $ 1 \le N \le 10^5 $
2. $ 1 \le W \le 10^4 $
3. $ 1 \le c_i \le 10^4 $
4. $ 0 \le r_i \le 1 $
**Objective**
Minimize the total cost:
$$
\min_{\sigma \in S_N} \sum_{i=1}^{N} c_{\sigma(i)} \cdot W \cdot \prod_{j=1}^{i-1} r_{\sigma(j)}
$$
where $ \sigma $ is a permutation of $ \{1, \dots, N\} $, representing the order of gun usage.