用dp的方法。

[t,k] = list(map(int,input().split()))

maxn = int(1e5 + 100)

dp = [[0]*2 for _ in range(maxn)]
dp[1][1] = 1
dp[k][0] = 1
ans = [0]*maxn

for i in range(1,100000):
    dp[i+k][0] += (dp[i][0] + dp[i][1])
    dp[i+1][1] += (dp[i][0] + dp[i][1])
    ans[i] = ans[i-1] + dp[i][0] + dp[i][1]
while t:
    [a,b] = list(map(int,input().split()))
    print(ans[b] - ans[a-1])
    t -= 1

最后不知道过了多少，快要交卷了