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
for ii in range(input()):
    import math
    ak=map(int,raw_input().split())
    n=ak[0]
    aks=map(int,raw_input().split())
    a=max(aks)
    k=math.factorial(n)
    ans= k%a
    print ans