#403 Overwrite Queries

Statement

Statement language

There is an array $A$ of length $N$ . Initially, $A_i=0$ for every $i$ .

You are also given a permutation $P$ of $1,2,\cdots,N$ and $Q$ queries. Query $i$ is described by three integers $l_{i}, r_{i}, x_{i}$ . When it is executed, is replaced by for every .

You must execute every one of the $Q$ queries exactly once. You may choose their execution order arbitrarily.

Maximize the number of positions $i$ satisfying $A_i=P_i$ after all queries have been executed.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print one integer: the maximum possible number of positions $i$ satisfying $A_i=P_i$ after all queries have been executed.

Constraints

$1 \le T \le 100$ .
$1 \le N \le 5\,000$ .
$1 \le Q \le 5\,000$ .

Subtasks

#	Score	Constraints
1	35	$N \le 400$ . $Q \le 400$ . The sum of $N$ over all test cases does not exceed $400$ .

Samples

Input

Output

1
3
2

In the first test case, whichever of the two queries is executed later overwrites the whole array, so at most one position can match the target permutation.

In the second test case, all three positions can be made correct by choosing a suitable order.