- Time limit: 1.00 s
- Memory limit: 512 MB
Your task is to efficiently calculate values modulo .
Note that in this task we assume that .
Input
The first input line contains an integer : the number of calculations.
After this, there are lines, each containing two integers and .
Output
Print each value modulo .
Constraints
Example
Input:
3 3 4 2 8 123 123
Output:
81 256 921450052