HABLU - Hablu and Bablu

no tags 

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(!) 1012 problems. So no number will be greater than 1012. 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: It may be impossible to pass the time limit in some languages.


hide comments
nadstratosfer: 2019-12-22 21:37:01

Couldn't beat WA until I assumed psetter must have lied about the bounds, and increased one of limits in my solution that subsequently got AC. A program designed to crash if any value is out of bounds also passed though, leaving me with no idea where the bug is. I've done hundreds of similar problems on SPOJ using the same functions as here and this never happened.

Note we're looking for number of valid *positive* integers that represent Bablu's record. This can be inferred from the sample but should be stated explicitly in the statement.

Python passes despite heavy testdata, good problem.

[Lakshman]: 2014-12-05 17:08:13

My best time with Pollard Rho + Miller Rabin .16s.

Last edit: 2014-12-05 17:12:32
Rohan Jain: 2014-12-05 12:21:24

getting tle with pollard rho+rabin miller
@fitcat, @XeRoN!X how did you do it..??

[Lakshman]: 2014-02-21 03:42:24

@mad Come to forum we can discuss.

newbie: 2014-02-20 12:15:21

@Lakshman can u provide some test cases

Last edit: 2014-02-20 12:16:17
[Lakshman]: 2014-02-20 09:31:39

Finally ACCEPTED!!!! after unlimited WA.

PubLic_AvenGeR: 2012-07-25 10:09:30

My O(sqrt(n)) passes in 0.87 ..Quite optimized one though.

Rajesh Kumar: 2012-07-25 10:09:30

Sherman Lehmer's O(n^1/3)..;)

fitcat: 2012-07-25 10:09:30

Pollard Rho + Fermat is fine.

XeRoN!X: 2012-07-25 10:09:30

Do not use pollard rho, it will TLE.
(pollard rho + miller rabin in my case)

Last edit: 2012-01-23 20:18:09

Added by:Bidhan
Date:2011-06-26
Time limit:1s
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.