Kotlin Heroes

The International Collegiate Programming Contest is an algorithmic programming contest for college students. This year, the $45^{th}$ ICPC event was held in Dhaka. The event is held for 5-6 days. In this mega event, there are programming contests and other events like tech showcase/chilling zone, cultural experience, ICPC Challenge, and lots more fun. The Kotlin Heroes contest is one of them.
Kotlin Heroes Contest: To unveil the full power of the Kotlin programming language and their advantages in algorithmic problem-solving, this year in the ICPC World Finals event, Kotlin Heroes contest also be held. The winner will be the Kotlin Hero.

Event Details: Thus, we’ve invited two competitive programming stars to match their skills in solving Kotlin problems on stage at the ICPC World Finals. There will be a single problem need to be solved. Andrew Ecnerwala, one of the top competitive programmers in the world, and will compete in a match against Kamil Errichto Debowski, Codeforces "Legendary Grandmaster" and Topcoder’s "Target." The match will be commentated on by none other than Roman Elizarov, Kotlin Lead Language Designer.

Problem Details: There is a race track of length N, in which the points are numbered from 0 to N. $M$ runners will participate in a race. Every runner has power $(1\le i \le m)$ $P_i$. Having $P_i$ power means the $i^{th}$ runner can only jump exactly $P_i$ points forward. This race is quite exceptional, as there are no winner. All the runners have to meet up at a single point on this race-track.

• Initially all the runners are in point 0, but this will not be regarded as a meeting point.

• A runner can either jump or wait for another runner for a meetup.

• If a runner decides to jump, then he can only jump exactly $P_i$ step forward.

Now, the race track contains lots of points (except the initial point) such that everyone can gather and make a meetup.
You have to tell how many points are in this race track such that all runners can gather and make a meetup.

Given the value of $N$ and $M$ runners’ power, you have to find such points where all runners can meet up.

Example:

N = 12, M = 2, P = { 2, 3 }

All the meetup points in this example are 6 and 12.

So, The number of meetup points for this race track will be 2.

Now, You have an opportunity to participate in this contest in an online mirror, the exception is that they can use only the Kotlin programming language but you can use any language.

Input

The first line of the input contains a single integer $T$ – the number of test cases. Then the test cases follow.

• The first line of each test case contains two integers $N$ — the length of the race track and $M$ — the number of runners.

• The second line of each test case contains $M$ separate integers  $P_1, P_2, P_3…. P_M$ — denoting the power of each runner.

$(1 \le T \le 100)$

$(1 \le N \le 10^{18})$

$(2 \le M \le 10)$

$(1 \le P_i \le 100)$

Output

For each test case output, the total number of points where all runners can gather and make a meetup.

Sample

Input	Output
3 12 2 2 3 100 2 2 3 20 3 1 5 10	2 16 2