Alice has a permutation p₁, p₂, ..., p_n of the integers 1, 2, ..., n. She performs q operations on it sequentially. Each operation is described by two integers x and y. If p_x > p_y, Alice swaps p_x and p_y.

Unfortunately Alice forgot what her initial permutation was, but she remembers that her permutation became sorted after performing all operations sequentially. Alice wants to recover her original permutation, but there could be many such permutations. Find the number of initial permutations such that after performing all operations it becomes sorted.

The first line will contain a single integer T, the number of test cases.

Each test case starts with a single line containing two integers n and q. Each of the next q lines contain two integers x and y.

Constraints

• 1 ≤ T ≤ 10
• 2 ≤ n ≤ 20
• 1 ≤ q ≤ 200
• Sum of q over all cases does not exceed 400
• 1 ≤ x, y ≤ n and x ≠ y

For each case, print single line containing the case number and an integer denoting the number of permutations which become sorted after all operations. See the sample for details.

For the first case, [1, 2, 3], [1, 3, 2], [2, 1, 3] and [3, 1, 2] are valid initial permutations.
For the second case, no initial permutation is valid.
For the third case, one valid permutation is [1, 3, 4, 2]. After the first operation it becomes [1, 4, 3, 2]. The second operation does not change it, After the third operation, it becomes [1, 2, 3, 4]. The last operation does not change it.