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 dos 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).