T=int(input())
for tests in range(T):
    N,X=map(int,input().split())

    if X%2==1:
        print(N//2)
    else:
        lo=(N+1)//(X+1)
        ANS=lo*(X//2+1)

        rest=N-lo*(X+1)
        print((ANS+(rest+1)//2)%mod)