After creating a colour palette, ohi is satisfied at leaves the room. But before she leaves, she seemingly drops a sheet of paper on the ground. You try to tell her that the page dropped, but there is no response. You pick up the paper. It's a list of demands. Seriously? Who gave her the power to trap people in her basement?

You read through the terrible handwriting and after a few minutes, you find out that she needs you to calculate really REALLY large exponents. However, a problem arises. She isn't allowed to use the BigInteger class (which surprisingly existed back in Java 1.4), so the numbers may very well exceed the "long" limit. However, she completely forgot about the limit and quickly typed up the solution, but to her surprise there were negative numbers being outputted!

You, knowing about the "long" limit, decides to take the modulus of the result to make sure the value does not exceed the limit. After some thinking, you decide on ~M~. I'm sure she won't notice the incorrect values after taking the modulus.

Constraints

~1\leq T\leq 10^5~

~10^6\leq M\leq 10^9+7~

~1\leq B_i\leq 10^6~

~1\leq E_i\leq 2^{63}-1~

Input Specifications

The first line will contain 2 space-separated integers, ~T,M~, where ~T~ is the number of test cases.

The next ~T~ lines will contain 2 space-separated integers, ~B_i,E_i~.

Output Specifications

For each of the ~T~ test cases, output ~B^E\; \textrm{mod}\; M~ on its own line.

Sample Input

4 1000000007
3 6
2 9
5 5
1 1000

Sample Output

729
512
3125
1