While Arya and Bran were playing together Bran decided to challenge Arya. He gave Arya a number n and asked her to find a number m greater than or equal to n such that if m is written in its binary form and the right most non-zero bit is made 0 it becomes smaller than n. Since there can be many such numbers Bran asked Arya to find kth smallest such number.Since Arya is busy training with Syrio Forel she wants you to find kth such number(smallest).Since the number to be reported can be very large, report it's modulo with 10^9 + 7 .

Input-
First Line contain t the number of test cases followed by t lines each containing 2 numbers n,k as described above.
Output-
Report kth such number m modulo (10^9+7).

Constraints-

0 < t < 10000
0 < n,k < 10^9

Example-
Input-
1
5 2
Output-
6

Explanation- 1st m is 5- since 5 is 101 in binary if last non zero one is made 0 it becomes 100 i.e. 4 which is smaller than 5
6 is 2nd such number since 6 is 110 if last 1 is made 0 then it becomes 100 i.e. 4 which is smaller than 5. Hence 6 is answer since we have to report 2nd such number.