Have you ever wondered where your suitcases go after you check them in at the airport? Just behind the curtain where they disappear lies a large hall filled with a complex system of platforms and conveyor belts that sort the luggage accordingly.

Bajtazar is responsible for evaluating the design of this hall at the newly planned Bajtszawa-Bitom airport. According to the plan, the hall will contain $n$ platforms, numbered with integers from $1$ to $n$. Each suitcase is initially intended to arrive at the first platform. From each platform, a certain number of one-way conveyor belts may lead to platforms with strictly higher numbers. If no conveyor belt leaves a platform, the suitcase, upon reaching it, is taken by airport staff and moved to the appropriate aircraft. If there are conveyor belts leaving a platform, their order is important: the first suitcase to reach such a platform will leave it via the first conveyor belt, the second will leave via the second, and so on. When a suitcase leaves a platform via the last of the conveyor belts leaving it, the next suitcase will again leave via the first one, and so on in a cycle.

After a suitcase is delivered to the first platform, its journey along the conveyor belts and its collection by the staff take place before the next suitcase reaches the first platform. In other words, at any given moment, at most one suitcase is traveling on the conveyor belts.

It can be observed that after receiving a certain number of suitcases, the airport system will "reset," meaning it will return to a state where every platform with outgoing conveyor belts will send the next suitcase out via the first one. Bajtazar wonders what the minimum positive number of suitcases is after which the system will reset. Help him and calculate this value!

Input

The first line of standard input contains a single integer $n$ ($1 \le n \le 100$), representing the number of platforms.

The next $n$ lines contain descriptions of the platforms. The $i$-th of these lines first contains a non-negative integer $r_i$, representing the number of conveyor belts leaving the $i$-th platform. If $r_i = 0$, then suitcases are collected manually by airport staff from that platform. If $r_i > 0$, then the same line continues with $r_i$ integers $l_{i,1}, l_{i,2}, \dots, l_{i,r_i}$ ($i < l_{i,1} < l_{i,2} < \dots < l_{i,r_i} \le n$), representing the numbers of the platforms to which the successive conveyor belts from the $i$-th platform lead. Suitcases leave the $i$-th platform via the conveyor belts in the order given in the input (and thus in increasing order of the destination platform numbers).

Output

The only line of output should contain a single integer representing the minimum positive number of suitcases that, after being delivered to the first platform, will cause the airport system to reset.

Examples

Input 1

7
3 2 3 5
2 3 6
3 5 6 7
1 6
1 7
0
0

Output 1

6

Input 2

3
0
1 3
0

Output 2

1

Note

Explanation of the examples: The layout of platforms and conveyor belts in the first example test looks as follows:

The routes taken by successive suitcases to their destination platforms are illustrated below:

After six suitcases, each platform will again send the next suitcase out via the first conveyor belt leaving it, so the answer is 6.

The layout of platforms and conveyor belts in the second example test looks as follows:

The first suitcase will be collected by airport staff directly from the first platform and will not change anything, so the system will be reset after just one suitcase.