Your task is very simple. Given K numbers A1, A2, ..., AK. You need to find f(N) mod max(A1, A2, ..., AK) .
f(N)=N!

Input

First line contains single integer T denoting the number of test cases..
First line of each test case contains two integers N and K.
Next line contains K integers Ak

Output
For each test case, print a single line containing desired output

Constraints

1 <= T <= 100
1 <= N <=100
1 <= K <=100000
1 <= Ak <=10^9

Example
Input:
1
5 3
200 6 9

Output:
120

见题面

见题面