Manoj is a geek who loves ciphering data. He is also known for doing stupid things like setting fire in his room like a caveman. One day he does that and accidentally throws a paper containing some sensitive information. However, he has the encrypted version of the data.

Each number in the original text is the number of pairs of integers A, B (A < B, 1 <= A, B <= N) such that their GCD Quotients match the given set of integers.

GCD Quotients of a pair (A, B) is defined as the sequence of quotients that are obtained while computing the GCD of A and B using Euclid's Algorithm. For example,

          GCD(7,9) =
          7) 9 (1
             7
            ---
             2) 7 (3
                6
               ---
                1) 2 (2
                   2
                  ---
                   0
                  ---

In the above example, the GCD quotient sequence is [1, 3, 2].

Input

The first line contains T, the number of test cases. Each test case contains two integers N and Q on the first line and Q integers on the second line, denoting the quotient sequence.

Output

For each test case, output the number of pairs of integers, whose GCD quotient sequence match with the given sequence.

Example

Input:
2
10 3
1 3 2
2 1
3

Output:
1
0

Explanation

For the first case, there exists only one such pair in the range [1, 10], which is (7, 9).

For the second case, the smallest possible pair is (1, 3), but since the given range is only [1, 2], hence we have zero such pairs.

Constraints

1 <= N <= 10¹⁶

1 <= Q <= 50

1 <= each quotient value <= 1000

1 <= T <= 10⁵

Product of all Quotient Values <= 10¹²

Note

A new test file has been added that includes some tricky test cases on 29/09/14 and all submissions were rejudged.

Please don't ask the answers for additional test cases in the comments. Figure out yourself.