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. 

hide comments
Apoorv Agarwal: 2014-10-02 13:32:20

Finally found the tricky case!! :D
Btw a nice one! Enjoyed solving!

shiv prasad chabarval: 2014-10-01 14:15:13

can't figure out why WA :(
checked all corner cases for (a<b)

Andy: 2014-10-01 14:15:13

--nitish--> Nice Catch.

Last edit: 2014-09-30 15:04:18
Jacob Plachta: 2014-10-01 14:15:13

Haha, nice "tricky case", I'm glad that was added.

--nitish--> Thanks :).

Last edit: 2014-09-30 14:59:09
ping_of_death: 2014-10-01 14:15:13

@nitish can u give any hint for tricky test case.

Andy: 2014-10-01 14:15:13

--nitish--> Fixed the test case.

Last edit: 2014-09-29 21:42:36
Rahul Jain: 2014-10-01 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: 2014-10-01 14:15:13

@Nitish, did u take any quotient value or any other value=0 ?

Last edit: 2014-09-29 12:10:29

Added by:nitish rao
Date:2014-09-28
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:My own Problem