MANJFIRE  Manoj and Fire
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 <= 10^{16}
1 <= Q <= 50
1 <= each quotient value <= 1000
1 <= T <= 10^{5}
Product of all Quotient Values <= 10^{12}
^{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. }
hide comments
Apoorv Agarwal:
20141002 13:32:20
Finally found the tricky case!! :D


shiv prasad chabarval:
20141001 14:15:13
can't figure out why WA :(


Andy:
20141001 14:15:13
nitish> Nice Catch. Last edit: 20140930 15:04:18 

Jacob Plachta:
20141001 14:15:13
Haha, nice "tricky case", I'm glad that was added.


ping_of_death:
20141001 14:15:13
@nitish can u give any hint for tricky test case. 

Andy:
20141001 14:15:13
nitish> Fixed the test case. Last edit: 20140929 21:42:36 

Rahul Jain:
20141001 14:15:13
I don't think if there is anything wrong in my code as long as you didn't take any value less than 1. 

Rahul Jain:
20141001 14:15:13
@Nitish, did u take any quotient value or any other value=0 ? Last edit: 20140929 12:10:29 
Added by:  nitish rao 
Date:  20140928 
Time limit:  1s2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  My own Problem 