Circle of Death

Abir is a school going boy, who loves math. Also, he loves to play with stones. Recently he invented a game.

Abir has infinite amount of stones. He takes N of them and arranges them in a circle. He marks them using numbers 1, 2, 3,... N. Stone 2 is next to stone number 1. And so on. As the stones are arranged in a circle, after the stone number N there is the first stone with stone number 1. He calls this the Circle of Death.

Now he takes out every second stone from the circle of death until there is only one stone left in the circle. For example, if he starts with 5 stones, he takes out the stones in the following order: First he skips the 1st stone and throws out the 2nd stone. Then he skips the 3rd stone and he throws out 4th stone. Then he skips the 5th stone and throws out the 1st stone. After this process, the only stone that was not thrown out is the stone number 3. Then he arranges another circle of death with 3 stones (as 3 was the number of only stone that was left in the last circle). And he again identifies the stone as 1, 2 and 3. Then he again throws away every second stone from the circle of death. The throwing process happens as this: 2 -> 1. And again 3 is the last stone that was not thrown out in this game. As the id of the stone that was left is the same as the number of stones he started with, he ends his game. Then he announces 3 as his favorite number.

To be precise, at first he takes N stones, and arranges them in a circle. Then he throws out every second stone in the circle until there is only one stone in the circle. If x1 is the id of last stone that is not thrown out, he first checks if x1 is the number of stones the circle had before he began throwing out the stones (in this case, the number is N). So he checks if x1 = N. If the both the numbers are equal, then he stops his game and decides that x1 is his favorite number. If the numbers are not equal he arranges x1 stones in a different new circle, and again, throws every second stone out. Then if the last stone that was not thrown out is x2, then he again checks if the number x2 is the number of stones he had in this circle. He had x1 stones before this round started. So he checks if x1 = x2. If the numbers are equal, he stops his game, and decides that x2 is his favorite number. Otherwise he continues the game with x2 stones. The game goes on like this until the result of a game starting with xi stones ends with a stone with id xi left. Then Abir decides that xi is his favorite number.

Initially, Abir started playing with N stones in a circle. After finishing his game, he found that x is his favorite number. Seeing this, his best friend Nabil also wants x to be his favorite number. He thought of the following question, How many different integers with value L are there, between 1 and 2K - 1(inclusive) such that if I played the game with L stones, I can also decide x as my favorite number just like Abir's? Can you help him? As the number can be very large, print it modulo (109 + 7)

Input

The first line will contain T. The number of test cases. Each of the next T lines will contain 2 integers each. Each line will contain the value of N and K separated with a space.

Constraints

1 ≤ T ≤ 10
1 ≤ N ≤ 1018
1 ≤ K ≤ 100000

Subtask 1(10 Points)
1 ≤ T ≤ 5
1 ≤ N ≤ 50
1 ≤ K ≤ 5

Subtask 2(20 Points)
1 ≤ T ≤ 10
1 ≤ N ≤ 1000000
1 ≤ K ≤ 5

Subtask 3(30 Points)
1 ≤ T ≤ 5
1 ≤ N ≤ 10000000
1 ≤ K ≤ 20

Subtask 4(40 Points)
Original Constraints

Output

For each of the test cases, you have to output the number of different integers with value L that is between 1 and 2K - 1 inclusive such that if the game was played with L stones, the favorite number will be same as the game is played with N stones. Print the answer modulo (109 + 7).

Sample

Input	Output
2 10 4 11 4	6 4