RIOI_2_2 - Switch

You are given array A of length N, initially all values in A are set to 0. We will make M passes through array. On ith pass we will visit cells B[i], 2*B[i], 3*B[i], and so on. In other words we visit cells that are multiples of B[i]. When we visit xth cell we change its value from 1 to 0 or from 0 to 1. That is if A[x] was 1 before visit, it changes to 0, or if it was 0 before visit it changes to 1.

After we make all M passes, we wonder what is the sum of the array.

Constraints

1 <= N, M <= 100000

B[i] <= N

Input

First line contains t, denoting number of tests. Each test looks as follows. First line consists of 2 integers, N and M, size of array and number of passes respectively. Second line consists of M integers denoting integer array B, which means that in ith pass we will visit cells that are multiples of B[i].

Output

Ouput t lines, solution to each test case.

Example

Input:
2
5 3
1 2 3
5 5
1 2 3 4 5
 
Output:
2
2

Added by:Buda IM
Date:2012-11-01
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.