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
from math import*
for i in range (input()):
    num ,k = map(int,raw_input().split())
    a = factorial(num)
    arr = map(int,raw_input().split())
    maxi = max(arr)
    print a%maxi