给定n个顶点m条边的有向图，每一条边上都有一个正整数权值。一条有向路径被称为上升路径当且仅当除了路径上第一条边外，每一条表上的权值都严格大于路径上前一条边的权值。路径长度定义为路径所包含的边数，求给定图中最长上升路径长度。

第一行是测试数据组数k。

接下来是k组测试数据。每组数据开始为n(n<=5000)和m(m<=100000)。接下来m行每行三个整数，表示图中一条边，格式为a b c，表示有一条从a到b的边，边权值为c。a和b是0到n-1的整数。

每个测试数据输出一行。输出图中最长上升路径长度。

2
3 4
0 1 1
1 2 1
0 1 2
1 2 2
4 4
0 1 1
1 3 1
0 2 2
2 3 2

2
1