def solution(N, K):
MOD = 10**9 + 7
# Initialize DP table
dp = [[0] * 2 for _ in range(N + 1)]
# Base cases
dp[0][0] = 1
for i in range(1, N + 1):
# Color the object with color 0
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD
# Color the object with color 1
dp[i][1] = dp[i - 1][0] # Always color the object with color 1 if possible
# If distance between previous object colored with 1 and current object <= K
if i >= K + 1:
dp[i][1] = (dp[i][1] + dp[i - K - 1][1]) % MOD
# Calculate total ways
total_ways = (dp[N][0] + dp[N][1]) % MOD
return total_ways
# Taking input from the user
T = int(input())
for _ in range(T):
N, K = map(int, input().split())
print(solution(N, K))
ZGVmIHNvbHV0aW9uKE4sIEspOgogICAgTU9EID0gMTAqKjkgKyA3CiAgICAKICAgICMgSW5pdGlhbGl6ZSBEUCB0YWJsZQogICAgZHAgPSBbWzBdICogMiBmb3IgXyBpbiByYW5nZShOICsgMSldCiAgICAKICAgICMgQmFzZSBjYXNlcwogICAgZHBbMF1bMF0gPSAxCiAgICAKICAgIGZvciBpIGluIHJhbmdlKDEsIE4gKyAxKToKICAgICAgICAjIENvbG9yIHRoZSBvYmplY3Qgd2l0aCBjb2xvciAwCiAgICAgICAgZHBbaV1bMF0gPSAoZHBbaSAtIDFdWzBdICsgZHBbaSAtIDFdWzFdKSAlIE1PRAogICAgICAgIAogICAgICAgICMgQ29sb3IgdGhlIG9iamVjdCB3aXRoIGNvbG9yIDEKICAgICAgICBkcFtpXVsxXSA9IGRwW2kgLSAxXVswXSAjIEFsd2F5cyBjb2xvciB0aGUgb2JqZWN0IHdpdGggY29sb3IgMSBpZiBwb3NzaWJsZQogICAgICAgIAogICAgICAgICMgSWYgZGlzdGFuY2UgYmV0d2VlbiBwcmV2aW91cyBvYmplY3QgY29sb3JlZCB3aXRoIDEgYW5kIGN1cnJlbnQgb2JqZWN0IDw9IEsKICAgICAgICBpZiBpID49IEsgKyAxOgogICAgICAgICAgICBkcFtpXVsxXSA9IChkcFtpXVsxXSArIGRwW2kgLSBLIC0gMV1bMV0pICUgTU9ECiAgICAKICAgICMgQ2FsY3VsYXRlIHRvdGFsIHdheXMKICAgIHRvdGFsX3dheXMgPSAoZHBbTl1bMF0gKyBkcFtOXVsxXSkgJSBNT0QKICAgIAogICAgcmV0dXJuIHRvdGFsX3dheXMKCiMgVGFraW5nIGlucHV0IGZyb20gdGhlIHVzZXIKVCA9IGludChpbnB1dCgpKQoKZm9yIF8gaW4gcmFuZ2UoVCk6CiAgICBOLCBLID0gbWFwKGludCwgaW5wdXQoKS5zcGxpdCgpKQogICAgcHJpbnQoc29sdXRpb24oTiwgSykpCg==