Byteland is a country whose population squares every year. The president of Byteland is aware of the situation and wants to take proper steps to control the population. For this he wants to estimate the population of the country for a given year. As President is weak in Math, He needs your help to solve this problem.

Input
First line of Input Contains T, the number of test cases.
For each test case there is a separate line containing two integers,The population of the country in the
year 2000(pi) and the year for which you have to find the population(yi).

Output
For each test case output on a separate line the expected population in the year yi.
As this can be very large find its modulo 10^9+7.

constraints
1 ≤ T ≤ 300
1 ≤ pi ≤ 10
2000 ≤ yi ≤ 2030

Example

Input:
2
5 2002
3 2000

Output:
625
3

见题面

见题面