腾讯第二题红花白花，超时统统会变成case通过率0%吗？

t,k = list(map(int,input().split()))
res = []
import math
def comb(n,m):
    return math.factorial(n)//(math.factorial(n-m)*math.factorial(m))
for i in range(t):
    a,b = list(map(int,input().split()))
    c = 0
    for j in range(a,b+1):
        d = j//k
        if d==0:
            c+=1
        else:
            for h in range(d+1):
                if h == 0:
                    e = 1
                elif j-h*k == 0:
                    e = 1
                else:
                    e = comb(j-h*k+h,h)
                c+=e
    res.append(int(c))
for m in range(len(res)):
    print(res[m])