Are You Lucky

All submissions for this problem are available.
Chef is very quick at finding remainders of integer division. Thus,to increase the difficulty, he is given three numbers X,Y and N,and asked to calculate the remainder of X^{Y}/N.
Note: Please look at the list of languages allowed for this problem.
Input
 The first line of the input contains an integer T denoting the number of test cases.
 The second line contains a single integer N denoting the divisor. Description of T cases follow.
 Each line of the test case contains 2 spaceseparated integers X and Y respectively.
Output
 For each test case, output a single line containing the remainder of (X^Y)/N.
Constraints
 1 ≤ T ≤ 10^6
 1 ≤ X ≤ 10^6
 1 ≤ Y,N ≤ 10
Example
Input: 3 3 5 2 2 5 3 3 Output: 1 2 0
Explanation
Example case 1. Here the value of N is 3, which remains constant for all test cases. The required output for the first test case would be the remainder of 5^{2}/3
i.e. 25%3
i.e. 1.
Author:  sichan 
Tags  sichan 
Date Added:  18092015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions