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

Difficulty: introductory

Starter code:

Solutions:
import sys
from collections import deque

input=sys.stdin.readline

t=1
t=int(input())
for _ in range(t):
    n=int(input())
    val=set([0,2*10**5+1])
    seg=[(0,2*10**5+1)]
    for i in range(n):
        l,r=list(map(int,input().split()))
        val.add(l)
        val.add(r)
        seg.append((l,r))
    val=list(val)
    val.sort()
    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)


import sys
from collections import deque

input=sys.stdin.readline

t=1
t=int(input())
for _ in range(t):
    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=list(val)
    val.sort()
    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)

import sys
from collections import deque

t=1
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=list(val)
    val.sort()
    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)

from collections import deque

t=1
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=list(val)
    val.sort()
    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)

from collections import deque

t=1
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)

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)

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)};deg=[0]*(n+1);out=[[] for i in range(n+1)]
    for i in range(n+1):l,r=seg[i];seg[i]=(comp[l],comp[r])    
    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);dp=[0]*(n+1)
    while deq:
        v=deq.popleft()
        for nv in out[v]:
            deg[nv]-=1
            if deg[nv]==0:deq.append(nv);ans.append(nv)    
    def solve(v):
        query=[[] for i in range(2*n+3)];subdp=[0]*(2*n+3)
        for nv in out[v]:l,r=seg[nv];query[r].append((l,dp[nv]))        
        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)

# Fast IO (only use in integer input)

# import os,io
# input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

t = int(input())
for _ in range(t):
    n = int(input())
    pointList = []
    pointOrderDict = {}
    interval = [] # (l,r) tuple
    intervalOrder = [] # interval list compressed as an order
    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): # r - l
        for j in range(cnt - i): # l
            ans1 = 0 # is there [l,r]
            ans2 = 0 # max of [l+1,r] and [l,nr] + [nr + 1,r]
            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 = list(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])
 


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))


def __starting_point():
    main()

__starting_point()

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

def put():
    return list(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()