/ ALGORITHM

玲珑杯 Round #17 problem B

Description

tang是一个咸鱼供应商，他告诉zhu在他那里面有N条咸鱼（标号从$1$到$N$）可以被用来制作.

zhu是一个特别的人，他有$M$个咸数（咸鱼数字）, 对于每个咸数$x$，他都会让所有满足标号是$x$倍数的咸鱼的咸鱼值异或上$1$.
zhu现在想知道经过了这$M$个咸数的筛选之后，最终有多少条的咸鱼的咸鱼值是$1$?

As we all know that Mr.zhu is a chef, and he has a unique salted fish making skills.
Mr.Tang is a salted fish supplier, he tells Mr.zhu that there are $N$ salted fishes (labeled from $1$ to $N$ ) which can be used to make it.
Each salted fish has a salted value $K_i$, and all $K_i$ are 0 at the beginning.
Mr.Zhu is a special person, he has a number of salons (salted fish value), for each salon $x$, he will let the salted value of all the salted fish whose label is the multiple of the $x$ xor by $1$.
Mr.Zhu now wants to know the final number of salted fish whose salted fish is $1$ after the $M$ salons of screening?

Input

The first line of the input contains an integer $T (1≤T≤1000)$ indicating that there is $T$ group data.
For each set of data:
The first line of the input contains only two integers $N (1≤N≤10^9), M (1≤M≤15)$.
The next line has $M$ integers, followed by Mr.zhu’s every salon $x (1≤x≤2 * 10 ^ 5)$.

Output

For each set of data, output the answer.

Sample Input

2
10 1
3
10 1
1


Sample Output

3
10


Solution

We define the number needed to XOR as the marked number, and the final XOR value is $1$ which corresponds to that the total marked times is odd.
For a certain salon $x$, it will mark all the salted fishes whose label is $x$’s multiple, so we plus the answer by $1 \times \frac{N}{x}$;
For the LCM of any two salons $x,y$, the salted fishes whose label is $LCM_{x,y}$’s multiple have been marked twice in the calculation of one salon, then the answer need to minus $2 \times \frac{N}{LCM_{x,y}}$;
For the LCM of any three salons $x, y, z$, the salted fishes whose label is $LCM_{x,y,z}$’s multiple have been marked $3$ times in the calculation of one salon, and are subtracted $6$ times when calculating two salons, then $(3-6 + t) = 1, t = 4$. so the answer need to add $4 \times \frac{N}{LCM_{x,y,z}}$.
And so on, we find that it needs reduction when the size of the salons is even and needs addition when the size of the salons is odd, each calculated coefficient is $2 ^ {the\ size\ of\ salons -1}$, and the final result is the size of the salt fishes whose marked times are odd.

AC code

Darron

The professional publishing platform