HABLU  Hablu and Bablu
Hablu is a hardworking programmer. He solves lots of easy problems everyday :P. Hablu's teammate Bablu is busy with studies, so amount of solved by him is smaller than Hablu's.
Their coach NannaMia noticed the fact that the number of solved problems by Hablu is a multiple of number of solved problems by Bablu.
Then NannaMia asked Hablu a question. Giving a collection of integers S, NannaMia said that the number of solved problems by Bablu is not a multiple of any integer contained in S (S only contains primes or 1). How many valid integers are there which could be the number of problems solved by Bablu.
As Hablu solves only easy problems, he is unable to solve this one. So, you need to help him :)
Input
The first line contains t, number of test cases (t<=1500).
Each case starts with an integer H, the number of problems solved by Hablu and K, the size of the collection S. The next line contains K space separated integers (the members of S).
Remember that the online judge in which they solve has only(!) 10^{12} problems. So no number will be greater than 10^{12}. And K will be between 0 and 500.
Output
Print a line for each test case containing the number of possible integers which can be the number of solved problems by Bablu.
Example
Input:
1
58 2
2 3
Output:
2
Note : May be it's impossible to pass the time limit in several languages.
hide comments
[Lakshman]:
20141205 17:08:13
My best time with Pollard Rho + Miller Rabin .16s. Last edit: 20141205 17:12:32 

Rohan Jain:
20141205 12:21:24
getting tle with pollard rho+rabin miller


[Lakshman]:
20140221 03:42:24
@mad Come to forum we can discuss. 

newbie:
20140220 12:15:21
@Lakshman can u provide some test cases Last edit: 20140220 12:16:17 

[Lakshman]:
20140220 09:31:39
Finally ACCEPTED!!!! after unlimited WA. 

Ashish Lavania:
20130507 17:20:56
Last edit: 20131221 17:38:21 

PubLic_AvenGeR:
20120725 10:09:30
My O(sqrt(n)) passes in 0.87 ..Quite optimized one though. 

Rajesh Kumar:
20120725 10:09:30
Sherman Lehmer's O(n^1/3)..;) 

fitcat:
20120725 10:09:30
Pollard Rho + Fermat is fine. 

XeRoN!X:
20120725 10:09:30
Do not use pollard rho, it will TLE.

Added by:  Bidhan 
Date:  20110626 
Time limit:  0.132s0.699s 
Source limit:  25000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem , Thanks to Muhammad Ridowan for his alternate solution. 