Efficient Algotithms 2022

Jasiu found on his hard drive an old game with the graceful name "Diamond Collector". The game is very primitive. It consists of walking on a board composed of square fields arranged in one line (a one-dimensional chessboard) and collecting diamonds on it. The game consists of several rounds. A round consists of spreading diamonds on the board; when the player reaches one of them he takes it, then all the diamonds disappear from the board and a new round with new diamonds begins (if in a new round a diamond appears on the field the player is standing on, it is automatically taken away and the next round begins). The idea is to go through all the rounds with as few steps as possible (a step - moving from one field to another).

The game has several levels, each offering a different board and a different distribution of diamonds in the rounds. The human starts each level standing on the field number 1, with 0 collected diamonds and 0 steps (regardless of what happened in previous levels).

Unfortunately, at the time when the game was created pseudo-random number generators had not been invented yet, so the levels have a predetermined appearance. Johnny, playing this game many times, managed to get to know it inside out and is able to pass each level in the smallest possible number of steps.

Write a program that tells how many steps Johnny takes on a given level of the game (assuming he plays optimally).

Input

In the first line of the input there is one integer d, denoting the number of levels of the game, and then the levels are described.

In the first line of the level description there are two integers N and M (1 ≤ N ≤ 500, 1 ≤ M ≤ 500), denoting the number of fields on the board and the number of rounds, respectively. Then there follow M lines with the description of successive rounds. The description of a round begins with the number n (1 ≤ n ≤ N), followed by n different (sorted ascendingly) integers from the range from 1 to N, denoting the numbers of squares on which there are diamonds (the squares are numbered starting from 1).

Output

Your program should output d integers, each in a separate line. The number in the i-th line should denote the number of steps needed for Johnny to reach the i-th level.

Example

Input:
3
2 3
1 2
2 1 2
1 1
3 3
1 3
1 2
1 1
5 4
2 2 5
3 1 3 5
1 4
5 1 2 3 4 5

Output:
2
4
3