Daenerys has an eye on the iron throne since a long time. As we all know, she has only 2 dragons left(sadly one is a white walker now). She decided to attack the Kings landing with her army and dragons. As Cersie came to know about this, she made a plan with Qyburn to defeat Daenerys.

Cersie appointed Qyburn as the commander of some soldiers whose numbers are always in the power of 2. Cersie gave him S = 2^N soldiers where soldiers are numbered from 0 to 2^N - 1.

Qyburn being a clever man, arranged the soldiers according to some rules. Arranging the soldiers in such a manner will increase the chances of Cersie's victory in the war.

The Qyburn's plan to arrange all the soldiers are as follows.

1. He will create some groups (of equal size) of S soldiers and arrange all the soldiers which are standing at even position next to each other. He will do the same for soldiers standing at odd positions. Relative order of the soldiers should be same during this arrangement.

2. He will then change the size of the group to S/2 and then repeat the step 1 for all groups till the size of all the groups comes to one.

Let N = 3. Then S = 2^3 = 8. Initial position of soldiers :-

| 0 1 2 3 4 5 6 7 |

Initially, S = 8, we will have only one group of 8 elements.

After arranging soldiers according to Rule 1:

| 0 2 4 6 | 1 3 5 7|

Now, S = S/2 = 4, so we will have 2 groups of 4 soldiers each.

After arranging soldiers according to Rule 1 in each group:

| 0 4 | 2 6 | 1 5 | 3 7 |

Now, S = S/2 = 2, so we will have 4 groups of 2 soldiers each.

After arranging soldiers according to Rule 1 in each group:

| 0 | 4 | 2 | 6 | 1 | 5 | 3 | 7 |

Now, S = S/2 = 1. So we will stop arranging soldiers.

Final positions of soldiers:

0 4 2 6 1 5 3 7

Bran saw Cersie and Qyburn talking about this plan in his vision and he wants to help Daenerys win the War but only if he can predict the arrangement of soldiers. To do so, he has to answer Q queries.

Let Ck and Dk be the original and final positions of soldier having number k initially. Each Query will be followed by two numbers X and Y. Bran has to find the value of

∑(|Ck - Dk| % M) where X<=k<=Y, M = 1000000007 and |a| denotes the absolute value of a.

But Bran being busy helping Jon Snow, he has asked you for the help.

Input Format:

First line contains T, the number of test cases. Each test case is followed by N and Q, the number Cersie gave to Qyburn and the number of queries.
Each Query contains X and Y, where X denotes the starting number of the soldier and Y denotes the number of last soldier.

Output Format:

For each query, print in new line the value of ∑(|Ck - Dk| % M).

Constraints:

1 <= T <= 4
1 <= N <= 16
1 <= Q <= 1000000
0 <= X <= Y <= 2^N-1