Sethi wants to take his girlfriend to a park on Valentine's Day. Every couple wants to go to the park on Valentine's Day. Thus seeing this opportunity the owner of the park changed his pricing.

The entry price of each ticket is increased every minute from just after the entrance to the park is opened. At the start of the day, it was 1$. After 1 minute it was still 1$. After 2, 3, 4, 5, 6 minutes it was 2$, 3$, 5$, 8$, 13$ respectively. And the cost of staying in the park follows the same procedure.

Suppose you entered at 3rd minute and left after 8th minute. So the entry fees is 3$ and for staying in for 5 minutes the cost was 5+8+13+21+34 i.e. 81$. Thus total cost is 84$.

Sethi is little weak at maths and wants to impress his girlfriend so he took help from HIREDIVE to calculate the total cost that he would have to have a perfect Valentines day.

Let's find out if you can do the same or not. You need to tell him the cost that he would have to pay. Since the total cost will be very large therefore you need to print cost MOD 10^9+7

INPUT:

The first line of input will be the number of test cases T. Next 'T' lines of input will contain two integers n and m where n is the time (in minutes) he enters the shop after the park has been opened and m is the time (in minutes) he spends in the park with his girlfriend.

OUTPUT:

Print 'T' lines, each containing only one integer as the answer.

CONSTRAINTS:

1<=T<=100
0<=N,M<=10^5