#include <fstream>
#include <vector>
#include <utility>
#include <array>
#include <string>
using namespace std;
 
array<array<int, 3501>, 3501> _buf;
class max_aib_2d{
	array<array<int, 3501>, 3501>& buf = _buf;
	const int sz;
public:
	max_aib_2d(const int n):
		sz(n){}
	~max_aib_2d(){
		for(int i = 1; i <= sz; ++i){
			for(int j = 1; j <= sz; ++j){
				buf[i][j] = 0; } } }
	void set(const int x, const int y, const int val){
		for(int xx = x; xx <= sz; xx += xx&-xx){
			for(int yy = y; yy <= sz; yy += yy&-yy){
				buf[xx][yy] = max(buf[xx][yy], val); } } }
	int get(const int x, const int y){
		int rez = 0;
		for(int xx = x; xx > 0; xx -= xx&-xx){
			for(int yy = y; yy > 0; yy -= yy&-yy){
				rez = max(rez, buf[xx][yy]); } }
		return rez; } };
 
int fa_test(ifstream& f, const int n){
	vector<pair<int, int> > cutii(n);
	string str;
	for(int i = 0, x; i < n; ++i){
		str.clear();
		getline(f, str);
		char *tmp = &str[0];
		x = strtol(tmp, &tmp, 10);
		cutii[x-1].first = strtol(tmp, &tmp, 10);
		cutii[x-1].second = strtol(tmp, &tmp, 10); }
	max_aib_2d lung_max(n);
	for(const auto c : cutii){
		lung_max.set(c.first, c.second, lung_max.get(c.first-1, c.second-1)+1); }
	return lung_max.get(n, n); }
 
int main(){
	ifstream f("cutii.in");
	ofstream g("cutii.out");
	int n, t;
	f >> n >> t >> ws;
	for(int i = 0; i < t; ++i){
		g << fa_test(f, n) << '\n'; }
	return 0; }