Time: 1000ms

The Problem

Mr Jiang gives Miss Zhao a problem about graphs. Unfortunately, she is not very good at graph theory.
However, she doesn't want to be looked down upon by Mr Jiang, who is always trying to laugh at her and call her "little fool".
Therefore, she turns to you for help.
There is a weighted directed graph which has n vertices and m edges. You should find a path with maximum number of edges, and the weight of each edge must be strictly greater than the weight of the provious one.

Print the number of edges in the path.
PS: There may be multiple edges with two nodes and self-loops in this graph.

Input

The first line of input is the number of test case.
Then for each case:
The first line contains two integers n,m(2<=n<=3*10^5;1<=m<=min(n*(n-1),3*10^5)).
Then, m lines follow. The i-th line contains three integers:
u,v,w(1<=u,v<=n;1<=w<=10^5) which indicates that there's a directed edge with weight w from vertex u to vertex v.

Output

Print a single integer. The length of the path.

Example Input

2
3 3
1 2 1
2 3 2
3 1 3
6 7
1 2 1
3 2 5
2 4 2
2 5 2
2 6 9
5 4 3
4 3 4

Example Output

3
6

Author

mrxy56