Leonid is developing new programming language. The key feature of his language is fast multiplication and raising to a power operations. He is asking you to help with the following task.
You have an expression S and positive integer M. S has the following structure: A1A2...An where "" is multiplication operation. Each Ai is an expression XiYi where Xi and Yi are non-negative integers and "" is raising Xi to power Yi operation.
.
Your task is just to find the value of an expression S modulo M

Input
The first line of the input contains an integer T denoting the number of test cases. Each of the following T testcases is described by one line which contains one positive integer M and expression S separated by whitespace.

Output
For each test case, output a single line containing one integer corresponding to value of S modulo M

Constraints

1 ≤ T ≤ 20
1 ≤ M ≤ 10^18
1 ≤ length of S ≤ 10^4
0 ≤ Xi, Yi ≤ 10^9997
It's guaranteed that there will not be 0**0 expression

Example
Input:
2
1000 23*31
100000 112*24
Output:
24
1936

见题面

见题面