You are given $n$ segments on a coordinate axis $OX$. The $i$-th segment has borders $[l_i; r_i]$. All points $x$, for which $l_i \le x \le r_i$ holds, belong to the $i$-th segment.

Your task is to choose the maximum by size (the number of segments) subset of the given set of segments such that each pair of segments in this subset either non-intersecting or one of them lies inside the other one.

Two segments $[l_i; r_i]$ and $[l_j; r_j]$ are non-intersecting if they have no common points. For example, segments $[1; 2]$ and $[3; 4]$, $[1; 3]$ and $[5; 5]$ are non-intersecting, while segments $[1; 2]$ and $[2; 3]$, $[1; 2]$ and $[2; 2]$ are intersecting.

The segment $[l_i; r_i]$ lies inside the segment $[l_j; r_j]$ if $l_j \le l_i$ and $r_i \le r_j$. For example, segments $[2; 2]$, $[2, 3]$, $[3; 4]$ and $[2; 4]$ lie inside the segment $[2; 4]$, while $[2; 5]$ and $[1; 4]$ are not.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 3000$) — the number of segments. The next $n$ lines describe segments. The $i$-th segment is given as two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le 2 \cdot 10^5$), where $l_i$ is the left border of the $i$-th segment and $r_i$ is the right border of the $i$-th segment.

Additional constraint on the input: there are no duplicates in the list of segments.

It is guaranteed that the sum of $n$ does not exceed $3000$ ($\sum n \le 3000$).


-----Output-----

For each test case, print the answer: the maximum possible size of the subset of the given set of segments such that each pair of segments in this subset either non-intersecting or one of them lies inside the other one.


-----Example-----
Input
4
4
1 5
2 4
2 3
3 4
5
1 5
2 3
2 5
3 5
2 2
3
1 3
2 4
2 3
7
1 10
2 8
2 5
3 4
4 4
6 8
7 7

Output
3
4
2
7

Source: codeforces | Difficulty: EASY


Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	pointList = []
	pointOrderDict = {}
	interval = []
	intervalOrder = []
	for _ in range(n):
		(l, r) = map(int, input().split())
		pointList.append(l)
		pointList.append(r)
		interval.append((l, r))
	pointList.sort()
	cnt = 0
	for i in range(2 * n):
		if i == 0 or pointList[i] != pointList[i - 1]:
			pointOrderDict[pointList[i]] = cnt
			cnt += 1
	for elem in interval:
		intervalOrder.append((pointOrderDict[elem[0]], pointOrderDict[elem[1]]))
	intervalList = []
	dp = []
	for i in range(cnt):
		dp.append([])
		intervalList.append([])
		for j in range(cnt):
			dp[i].append(-1)
	for elem in intervalOrder:
		intervalList[elem[0]].append(elem[1])
	for i in range(cnt):
		for j in range(cnt - i):
			ans1 = 0
			ans2 = 0
			if i != 0:
				ans2 = dp[j + 1][i + j]
			for elem in intervalList[j]:
				if elem == i + j:
					ans1 += 1
				elif elem < i + j and ans2 < dp[j][elem] + dp[elem + 1][i + j]:
					ans2 = dp[j][elem] + dp[elem + 1][i + j]
			dp[j][i + j] = ans1 + ans2
	print(dp[0][cnt - 1])


import sys
for _ in range(int(input())):
	M = int(input())
	LR_raw = []
	val = set()
	for _ in range(M):
		(l, r) = map(int, input().split())
		LR_raw.append((l, r))
		val.add(l)
		val.add(r)
	val = sorted(list(val))
	val2idx = {x: i for (i, x) in enumerate(val)}
	LR = []
	N = len(val)
	segment = [set() for _ in range(N)]
	for (l_, r_) in LR_raw:
		l = val2idx[l_]
		r = val2idx[r_]
		LR.append((l, r))
		segment[l].add(r)
	dp = [[0] * N for _ in range(N)]
	for d in range(1, N + 1):
		for l in range(N):
			r = l + d - 1
			if r < N:
				if l + 1 <= r:
					dp[l][r] = dp[l + 1][r]
				for rr in segment[l]:
					if rr >= r:
						continue
					dp[l][r] = max(dp[l][r], dp[l][rr] + dp[rr + 1][r])
				if r in segment[l]:
					dp[l][r] += 1
	print(dp[0][-1])


from bisect import bisect_left as lower
import sys
input = sys.stdin.readline

def put():
	return map(int, input().split())

def func(size, seg):
	dp = [[0] * size for i in range(size)]
	for k in range(1, size + 1):
		for l in range(size):
			r = l + k - 1
			if r < size:
				if l + 1 <= r:
					dp[l][r] = dp[l + 1][r]
				same = 0
				for i in seg[l]:
					if i == r:
						same = 1
					if i < r:
						dp[l][r] = max(dp[l][r], dp[l][i] + dp[i + 1][r])
				dp[l][r] += same
	return dp[0][-1]

def solve():
	t = int(input())
	for _ in range(t):
		n = int(input())
		(l, r, m) = ([], [], set())
		for i in range(n):
			(x, y) = put()
			l.append(x)
			r.append(y)
			m.add(x)
			m.add(y)
		m = sorted(m)
		size = len(m)
		seg = [[] for i in range(size)]
		for i in range(n):
			l[i] = lower(m, l[i])
			r[i] = lower(m, r[i])
			seg[l[i]].append(r[i])
		print(func(size, seg))
solve()


from collections import deque
for _ in range(int(input())):
	n = int(input())
	val = set([0, 2 * 10 ** 5 + 1])
	seg = [(0, 2 * 10 ** 5 + 1)]
	for i in range(n):
		(l, r) = map(int, input().split())
		val.add(l)
		val.add(r)
		seg.append((l, r))
	val = sorted(list(val))
	comp = {i: e + 1 for (e, i) in enumerate(val)}
	for i in range(n + 1):
		(l, r) = seg[i]
		seg[i] = (comp[l], comp[r])
	deg = [0] * (n + 1)
	out = [[] for i in range(n + 1)]
	for i in range(n + 1):
		for j in range(i + 1, n + 1):
			(l, r) = seg[i]
			(L, R) = seg[j]
			if L <= l and r <= R:
				out[j].append(i)
				deg[i] += 1
			elif l <= L and R <= r:
				out[i].append(j)
				deg[j] += 1
	ans = [0]
	deq = deque(ans)
	while deq:
		v = deq.popleft()
		for nv in out[v]:
			deg[nv] -= 1
			if deg[nv] == 0:
				deq.append(nv)
				ans.append(nv)
	dp = [0] * (n + 1)

	def solve(v):
		query = [[] for i in range(2 * n + 3)]
		for nv in out[v]:
			(l, r) = seg[nv]
			query[r].append((l, dp[nv]))
		subdp = [0] * (2 * n + 3)
		for i in range(1, 2 * n + 3):
			res = subdp[i - 1]
			for (l, val) in query[i]:
				test = subdp[l - 1] + val
				res = max(test, res)
			subdp[i] = res
		dp[v] = subdp[-1] + 1
	for v in ans[::-1]:
		solve(v)
	print(dp[0] - 1)


def f(sl):
	sl.sort(key=lambda s: (s[1], -s[0]))
	tl = sorted(list(set([s[0] for s in sl] + [s[1] for s in sl])))
	cd = {tl[i]: i for i in range(len(tl))}
	csl = [[] for i in range(len(tl))]
	for (s0, s1) in sl:
		csl[cd[s1]].append(cd[s0])
	dp = [[len(csl[0])]]
	for r in range(1, len(tl)):
		dp.append(dp[-1] + [0])
		for li in csl[r]:
			dp[r][li] += 1
			for l in range(li):
				dp[r][l] = max(dp[r][l], dp[r][li] + dp[li - 1][l])
	return dp[-1][0]
T = int(input())
for i in range(T):
	n = int(input())
	ll = [list(map(int, input().split())) for _ in range(n)]
	print(f(ll))


import sys
input = sys.stdin.buffer.readline

def solve():
	n = int(input())
	LR = [tuple(map(int, input().split())) for i in range(n)]
	s = set()
	for (l, r) in LR:
		s.add(l)
		s.add(r)
	dic = {x: i for (i, x) in enumerate(sorted(list(s)))}
	le = len(s)
	seg = [[] for i in range(le)]
	for (l, r) in LR:
		seg[dic[r]].append(dic[l])
	dp = [[len(seg[0])]]
	for i in range(1, le):
		dp.append(dp[-1] + [0])
		for l in sorted(seg[i], reverse=True):
			dp[i][l] += 1
			for j in range(l):
				dp[i][j] = max(dp[i][j], dp[i][l] + dp[l - 1][j])
	return dp[-1][0]
t = int(input())
for _ in range(t):
	ans = solve()
	print(ans)


def solve():
	n = int(input())
	LR = [tuple(map(int, input().split())) for i in range(n)]
	LR.sort(key=lambda x: (x[1], -x[0]))
	s = set()
	for (l, r) in LR:
		s.add(l)
		s.add(r)
	dic = {x: i for (i, x) in enumerate(sorted(list(s)))}
	le = len(s)
	seg = [[] for i in range(le)]
	for (l, r) in LR:
		seg[dic[r]].append(dic[l])
	dp = [[len(seg[0])]]
	for i in range(1, le):
		dp.append(dp[-1] + [0])
		for l in seg[i]:
			dp[i][l] += 1
			for j in range(l):
				dp[i][j] = max(dp[i][j], dp[i][l] + dp[l - 1][j])
	return dp[-1][0]
t = int(input())
for _ in range(t):
	ans = solve()
	print(ans)


from operator import itemgetter
import bisect
import sys
input = sys.stdin.buffer.readline

def topological_sort(graph: list) -> list:
	n = len(graph)
	degree = [0] * n
	for g in graph:
		for next_pos in g:
			degree[next_pos] += 1
	ans = [i for i in range(n) if degree[i] == 0]
	q = ans[:]
	while q:
		pos = q.pop()
		for next_pos in graph[pos]:
			degree[next_pos] -= 1
			if degree[next_pos] == 0:
				q.append(next_pos)
				ans.append(next_pos)
	return ans

def solve_dp(ds):
	n = len(ds)
	dp = [0] * (len(ds) + 1)
	ls = [l for (l, r) in ds]
	rs = [r for (l, r) in ds]
	for i in range(n):
		(l, r) = ds[i]
		ind = bisect.bisect_left(rs, l)
		dp[i + 1] = max(dp[ind] + vals[to_ind[l, r]], dp[i])
	return max(dp)
t = int(input())
for _ in range(t):
	n = int(input())
	dists = [list(map(int, input().split())) for i in range(n)]
	dists.sort(key=itemgetter(1))
	to_ind = {(l, r): i for (i, (l, r)) in enumerate(dists)}
	graph = [[] for i in range(n)]
	for i in range(n):
		(li, ri) = dists[i]
		for j in range(n):
			if i == j:
				continue
			(lj, rj) = dists[j]
			if li <= lj <= rj <= ri:
				graph[i].append(j)
	tp_sort = topological_sort(graph)
	vals = [0] * n
	for v in tp_sort[::-1]:
		ds = []
		for nxt_v in graph[v]:
			ds.append(dists[nxt_v])
		vals[v] = solve_dp(ds) + 1
	print(solve_dp(dists))


import sys

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s)
	sys.stdout.write('\n')

def wi(n):
	sys.stdout.write(str(n))
	sys.stdout.write('\n')

def wia(a, sep=' '):
	sys.stdout.write(sep.join([str(x) for x in a]))
	sys.stdout.write('\n')

def solve(n, segs):
	vals = set()
	for (l, r) in segs:
		vals.add(l)
		vals.add(r)
	vals = sorted(list(vals))
	d = {x: i for (i, x) in enumerate(vals)}
	m = len(vals)
	c_segs = []
	r_segs = [[] for _ in range(m)]
	for (l, r) in segs:
		ll = d[l]
		rr = d[r]
		c_segs.append((ll, rr))
		r_segs[ll].append(rr)
	dp = [[0] * m for _ in range(m)]
	for ln in range(1, m + 1):
		for l in range(m):
			r = l + ln - 1
			if r >= m:
				continue
			if l + 1 <= r:
				dp[l][r] = dp[l + 1][r]
			for rr in r_segs[l]:
				if rr >= r:
					continue
				dp[l][r] = max(dp[l][r], dp[l][rr] + dp[rr + 1][r])
			if r in r_segs[l]:
				dp[l][r] += 1
	return dp[0][-1]

def main():
	for _ in range(ri()):
		n = ri()
		segs = []
		for i in range(n):
			(l, r) = ria()
			segs.append((l, r))
		wi(solve(n, segs))
main()


for _ in range(int(input())):
	n = int(input())
	P = [list(map(int, input().split())) for _ in range(n)]
	val = sorted([x[0] for x in P] + [x[1] for x in P])
	d = {}
	for x in val:
		if x not in d:
			d[x] = len(d)
	N = len(d)
	dp = [[0] * N for _ in range(N)]
	G = {}
	for (x, y) in P:
		(mX, mY) = (d[x], d[y])
		if mX not in G:
			G[mX] = []
		G[mX].append(mY)
		if mX == mY:
			dp[mX][mY] = 1
	for r in range(N):
		for l in range(r - 1, -1, -1):
			val1 = dp[l + 1][r]
			val2 = 0
			plus = 0
			if l in G:
				for r_ in G[l]:
					if r_ < r:
						val2 = max(val2, dp[l][r_] + dp[r_ + 1][r])
					if r_ == r:
						plus = 1
			dp[l][r] = plus + max(val1, val2)
	print(dp[0][-1])


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.buffer.readline
	for _ in range(int(input())):
		M = int(input())
		LR_raw = []
		val = set()
		for _ in range(M):
			(l, r) = map(int, input().split())
			LR_raw.append((l, r))
			val.add(l)
			val.add(r)
		val = sorted(list(val))
		val2idx = {x: i for (i, x) in enumerate(val)}
		LR = []
		N = len(val)
		segment = [set() for _ in range(N)]
		for (l_, r_) in LR_raw:
			l = val2idx[l_]
			r = val2idx[r_]
			LR.append((l, r))
			segment[l].add(r)
		dp = [[0] * N for _ in range(N)]
		for d in range(1, N + 1):
			for l in range(N):
				r = l + d - 1
				if r < N:
					if l + 1 <= r:
						dp[l][r] = dp[l + 1][r]
					for rr in segment[l]:
						if rr >= r:
							continue
						dp[l][r] = max(dp[l][r], dp[l][rr] + dp[rr + 1][r])
					if r in segment[l]:
						dp[l][r] += 1
		print(dp[0][-1])
main()