## MANJFIRE - Manoj and Fire

no tags

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) =           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`
`Explaination:`
`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 <= 1016`
`1 <= Q <= 50`
`1 <= each quotient value <= 1000`
`1 <= T <= 105`
`Product of all Quotient Values <= 1012`
`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. `