Description

Let $N = \{1, 2, \dots, n\}$ be a set consisting of the first $n$ positive integers. Let $Y = \{Y_1, Y_2, \dots, Y_m\}$ be a sequence of $m$ subsets of $N$, such that for any $1 \le p < q \le m$, $Y_p \not\subseteq Y_q$, meaning $Y_p$ is not a subset of $Y_q$.

For any $1 \le p < q \le m$ and $x \in N$, the score function $f_{p,q}(x)$ for sets $Y_p$ and $Y_q$ is defined as:

$$f_{p,q}(x) = \begin{cases} 1 & \text{if } x \in N \setminus Y_q \text{ and } Y_p \subseteq Y_q \cup \{x\} \\ 0 & \text{otherwise} \end{cases}$$

The thickness $\delta(Y)$ of the sequence $Y = \{Y_1, Y_2, \dots, Y_m\}$ is defined as:

$$\delta(Y) = \sum_{1 \le p < q \le m} \sum_{x=1}^n f_{p,q}(x)$$

The problem of finding the thickness of a sequence is to calculate $\delta(Y)$ for a given sequence $Y = \{Y_1, Y_2, \dots, Y_m\}$.

For example, when $N = \{1, 2, 3, 4, 5\}$ and $Y = \{Y_1, Y_2, Y_3\}$ where $Y_1 = \{1, 5\}$, $Y_2 = \{1, 2, 3\}$, and $Y_3 = \{2, 3, 5\}$, we have $f_{1,2}(5) = 1$, $f_{1,3}(1) = 1$, and $f_{2,3}(1) = 1$. Therefore, the thickness of the sequence $Y$ is $\delta(Y) = 3$.

Input

The input contains multiple test cases. The first line of each test case contains two positive integers $n$ and $m$ ($1 \le n \le 23000$, $1 \le m \le 10000$), representing the set $N = \{1, 2, \dots, n\}$ and the sequence $Y$ containing $m$ subsets of $N$.

The next $m$ lines describe the elements of the sets in $Y$. The first number in the $i$-th line is the number of elements in $Y_i$, followed by the elements of $Y_i$.

For 40% of the data, $\sum |Y_i| \le 6000$. For 100% of the data, $\sum |Y_i| \le 60000$.

Output

For each test case, output the calculated thickness of the sequence on a single line.

Examples

Input 1

5 3
2 1 5
3 1 2 3
3 2 3 5
5 10
2 1 5
3 1 2 3
3 2 3 5
2 2 4
2 3 5
1 1
1 2
1 3
1 4
1 5

Output 1

3
21