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