Setting

Suppose that the political student parties that constitute the student parliament at our university had the power to call for compulsory student party days: days on which all teaching ceases and students are forced to drink. Further suppose that each student party is characterized by a positive integer \(p\) called the party parameter that denotes the number of days between two consecutive student parties called by the given student party.

As an example, consider three student parties: the Student People's Front, the People's Front of Students, and the Back of People Who Were Students. Assume \(p(1)=3\), \(p(2)=4\), \(p(3)=8\), where \(p(i)\) is the party parameter for party \(i\). We can simulate the behavior of these three parties for \(N=14\) days. We always start the simulation on a Monday. There are no parties on either Saturdays or Sundays (because nobody fancies fun on their weekends). In our example, there will be exactly five parties (on days 3, 4, 8, 9, and 12) over the 14 days. There is no party on day 6 since it falls on a Saturday. Hence we lose five working days in two weeks.

Given the party parameters for several political parties and the value of \(N\), determine the number of working days lost 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 \(7 \leq N \leq 3650\), giving the number of days over which the simulation must be run. The next line contains another integer \(1 \leq P \leq 100\) representing the number of student parties. The next \(P\) lines contain the party parameters \(p(i)\) (which will never be a multiple of 7) for each party \(1 \leq i \leq P\).

Output

For each test case, output the number of working days lost on a separate line.

Sample Input

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

Sample Output

5
15

This is challenge 10050 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.

Statistics

Difficulty (1 vote)
Average test runtime 0.22
Points (changes over time) 10
Tried by 8 users
Solved by 7 users

Global ranking

# Name Runtime Points worth
1 贝尔恩德 0.12 16
2 ,s/java/NaN/gi 0.13 14
3 Irfan 0.15 13
4 Chris Danger 0.20 9
5 Mac 0.29 6
6 Dark 0.29 6
7 IeM 0.39 5