Doremy's Drying Plan (Easy Version)
The only differences between the two versions of this problem are the constraint on $$$k$$$, the time limit and the memory limit. You can make hacks only if all versions of the problem are solved.Doremy lives in a rainy country consisting of $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$.The weather broadcast predicted the distribution of rain in the next $$$m$$$ days. In the $$$i$$$-th day, it will rain in the cities in the interval $$$[l_i, r_i]$$$. A city is called dry if it will never rain in that city in the next $$$m$$$ days.It turns out that Doremy has a special power. She can choose $$$k$$$ days (in the easy version, $$$k = 2$$$), and during these days it will not rain. Doremy wants to calculate the maximum number of dry cities after using the special power.
In the first test case, if Doremy prevents  rain $$$1,2$$$, then city $$$2$$$ will be dry;  rain $$$2,3$$$, then no city will be dry;  rain $$$1,3$$$, then no city will be dry; So there is at most $$$1$$$ dry city.In the second test case, if Doremy prevents  rain $$$1,2$$$, then city $$$1,2$$$ will be dry;  rain $$$2,3$$$, then city $$$4,5$$$ will be dry;  rain $$$1,3$$$, then city $$$1,5$$$ will be dry. So there are at most $$$2$$$ dry cities.In the third test case, it is optimal to prevent rain $$$2,5$$$.In the forth test case, there is always $$$4$$$ days of rain that wets all the cities and cannot be prevented.
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of the test cases follows.The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$2 \le m \le 2\cdot 10^5$$$, $$$k = 2$$$) — the number of cities, the number of days, and the number of days of rain that Doremy can prevent.Then, $$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — the rain coverage on day $$$i$$$.It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2\cdot 10^5$$$.
For each test case, output one integer — the maximum number of dry cities.
import io, os
import bisect
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
    (n, m, k) = map(int, input().split())
    segs = []
    dp = [0] * (n + 1)
    for _ in range(m):
        (l, r) = map(int, input().split())
        l -= 1
        r -= 1
        dp[l] += 1
        dp[r + 1] -= 1
        segs.append((l, r))
    possible = []
    base = 0
    for i in range(n):
        if i > 0:
            dp[i] += dp[i - 1]
        if dp[i] == 0:
            base += 1
        elif dp[i] <= 2:
            possible.append(i)
    p = len(possible)
    condition = [[] for _ in range(p)]
    choices = []
    for (i, (l, r)) in enumerate(segs):
        locl = bisect.bisect_left(possible, l)
        locr = bisect.bisect(possible, r)
        for j in range(locl, locr):
            condition[j].append(i)
        if locr > locl:
            choices.append(i)
    single = {}
    double = {}
    for ele in condition:
        if len(ele) == 1:
            if ele[0] not in single:
                single[ele[0]] = 0
            single[ele[0]] += 1
        else:
            if tuple(ele) not in double:
                double[tuple(ele)] = 0
            double[tuple(ele)] += 1
    sdata = []
    for key in single:
        sdata.append(single[key])
    sdata.sort()
    ans = base
    if len(sdata) > 0:
        ans += sdata[-1]
    if len(sdata) > 1:
        ans += sdata[-2]
    for key in double:
        curr = double[key] + base
        if key[0] in single:
            curr += single[key[0]]
        if key[1] in single:
            curr += single[key[1]]
        ans = max(ans, curr)
    print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1
import sys
ipt = sys.stdin.readline
from collections import defaultdict

def iin():
    return int(ipt())

def lmin():
    return list(map(int, ipt().split()))
for _ in range(iin()):
    (N, M, K) = lmin()
    S = set()
    E = [[] for _ in range(N + 1)]
    for i in range(M):
        (l, r) = lmin()
        E[l - 1].append(i)
        E[r].append(~i)
    ans = 0
    d = defaultdict(int)
    S = set()
    cnt = 0
    sm = [0] * M
    for i in range(N):
        for e in E[i]:
            if e >= 0:
                S.add(e)
                cnt += 1
            else:
                S.remove(~e)
                cnt -= 1
        if cnt == 0:
            ans += 1
        elif cnt == 1:
            sm[list(S)[0]] += 1
        elif cnt == 2:
            d[tuple(sorted(S))] += 1
    ma = ans + sum(sorted(sm)[-2:])
    for (k, v) in d.items():
        (i, j) = k
        ma = max(ma, ans + v + sm[i] + sm[j])
    print(ma)
import sys
import heapq
from collections import *

def solute():
    starts = defaultdict(list)
    ends = defaultdict(list)
    (n, m, k) = map(int, sys.stdin.readline().split())
    for i in range(m):
        (l, r) = map(int, sys.stdin.readline().split())
        starts[l].append(i)
        ends[r + 1].append(i)
    if m == 2:
        return n
    res = 0
    curr = set()
    ones = defaultdict(int)
    twos = defaultdict(int)
    for t in range(1, n + 1):
        for i in starts[t]:
            curr.add(i)
        for i in ends[t]:
            curr.discard(i)
        if len(curr) == 0:
            res += 1
        elif len(curr) == 1:
            ones[tuple(curr)] += 1
        elif len(curr) == 2:
            twos[tuple(sorted(curr))] += 1
    new_ones = defaultdict(int)
    for (k, v) in ones.items():
        new_ones[k[0]] = v
    add = 0
    for (k, v) in twos.items():
        curr = v
        (i, j) = tuple(k)
        curr += new_ones[i] + new_ones[j]
        if curr > add:
            add = curr
    if new_ones:
        curr = sum(sorted(new_ones.values(), reverse=True)[:2])
        if curr > add:
            add = curr
    return res + add
t = int(sys.stdin.readline())
for _ in range(t):
    print(solute())