You are given a program P that manipulates an array of n elements (the elements are arbitrary natural numbers). We will use x[ i ] to denote the current value of array element i, for 1 \le i \le n. The program consists of m "compare" operations: s(i,j) swaps x[ i ] and x[ j ] if x[ i ] > x[ j ].

We say that program P is a sorter if, given any input array (arbitrary elements in an arbitrary order), after running P, all elements are in a nondecreasing order, that is, x[1] \le x[2] \le \dotso \le x[n].

Now the program that you are given may not be a sorter. However, repeating the same program for some k number of times might give a sorter!

Your task is to find the smallest k such that the program formed by concatenating k copies of P is a sorter, or report that such a k does not exist.

Input

The first input line has an integer t: the number of test cases.

Each test case starts with a line with two integers n and m. After that you will have a description of the program: there are m lines, each line with two numbers, i and j. Such a line denotes a compare operation s(i,j).

Output

For each test case, print one integer k: the smallest number of repetitions of the program that are needed to form a sorter. If such a number does not exist, print -1.

Limits

• 1 \le t \le 10
• 1 \le n \le 15
• 1 \le m \le 1500
• 1 \le i < j \le n

Example

Input:

3
4 4
1 2
3 4
1 2
3 4
4 3
1 2
2 3
3 4
2 1
1 2

Output:

-1
3
1

Explanations:

• First test case: If you give the input (3,4,1,2), the program does not ever change it, no matter how many times you repeat it.
• Second test case: If you start with input (4,3,2,1), one iteration of the program changes it to (3,2,1,4), which is not yet good. Another iteration changes it to (2,1,3,4), which is not yet good. However, after three iterations any input will be correctly sorted.
• Third test case: The input is already a sorter, one iteration is enough.