Agrim and Naman live in a strange world of strings.
Today Naman challenges Agrim to find all Secret strings of length N.

A string is called Secret string if:
1. It only contains 'A' and 'J'.
2. It does not have leading 'A' letters.
3. It does not contain X consecutive 'A' letters.

Since Agrim is busy in some research, help him find the total number of Secret strings of length N.

Input :
    The first line contains the number of test cases T. 
    Each test case consists of two space-separated integers -> N and X.

Output :
    For each test case output total number of Secret strings of length N modulo 1000000007(10^9+7).