Problem D: Hartals

Consider three political parties. Assume h₁ = 3, h₂ = 4 and h₃ = 8 where h_i is the hartal parameter for party i ( i = 1, 2, 3). Now, we will simulate the behavior of these three parties for N = 14 days. One must always start the simulation on a Sunday and assume that there will be no hartals on weekly holidays (on Fridays and Saturdays).

The simulation above shows that there will be exactly 5 hartals (on days 3, 4, 8, 9 and 12) in 14 days. There will be no hartal on day 6 since it is a Friday. Hence we lose 5 working days in 2 weeks.

In this problem, given the hartal parameters for several political parties and the value of N, your job is to determine the number of working days we lose in those N days.

Input 

The first line of the input consists of a single integer T giving the number of test cases to follow.

The first line of each test case contains an integer N ( ) giving the number of days over which the simulation must be run. The next line contains another integer P ( ) representing the number of political parties in this case. The i­th of the next P lines contains a positive integer h_i (which will never be a multiple of 7) giving the hartal parameter for party i ( ).

Output 

For each test case in the input output the number of working days we lose. Each output must be on a separate line.

Sample Input 

2
14
3
3
4
8
100
4
12
15
25
40

Sample Output 

5
15

#include<stdio.h>
int main() {
	int T, N, P;
	scanf("%d", &T);
	while(T--) {
		int Day[3651] = {0}, i, x, tmp;
		scanf("%d %d", &N, &P);
		for(i = 0; i < P; i++) {
			scanf("%d", &x), tmp = x;
			while(x <= N)
				Day[x] = 1, x = x+tmp;
		}
		int count = 0;
		for(i = 1; i <= N; i++)
			if(Day[i] == 1 && i%7 != 0 && i%7 != 6)
				count++;
		printf("%d\n", count);
	}
    return 0;
}