TJOUR_t_py

t = int(input())
for _ in range(t):
    n,k=map(int,input().split())
    v = []
    for i in range(n):
        x,y=map(int,input().split())
        v.append([x,1])
        v.append([y,-1])

    v.sort()
    cur=0
    maxv=0
    for i in range(len(v)):
        if(v[i][1] == 1):
            cur+=1
        else:
            cur-=1
        maxv = max(maxv, cur)


    ans=(maxv+k-1)//k
    print(ans)