For this problem we say our warmest thanks to Clive Fraser!
Bob is a scientist who is carrying out research into plant growth under varying conditions.
A typical study consists of N plants (numbered 1 to N). A number of processes need to be carried out with
the plants but these will be started at different times for each plant. Bob decides that a particular process
will be started on day 1 with plant 1. The process will be started with plant 8 on day 2, with plant 15
on day 3 and so on, each day moving 7 plants further along. When Bob comes to plant N, counting continues
by wrapping back to plant 1. Bob does not want to repeat the process with the same set of plants again. This
will happen if the number N is a multiple of 7. For example, if N = 21 then the plant numbers chosen,
in order, are 1, 8, 15, 1, 8, 15, 1, ... However, if N = 24 the plant numbers chosen are
1, 8, 15, 22, 5, 12, 19, 2, 9, 16, 23, ... In this latter case every plant will have been chosen once
before the sequence repeats. This is an important requirement of the study.
Bob has a number of different processes to carry out with the plants. The same procedure will be used for each
process but a different prime number will be chosen for each process. The prime number will determine the
separation of plants between applications of the process from one day and the next. The starting plant number
for each process will be chosen at random. No decision has yet been made on the number N of plants in the
study. The prime numbers associated with each process will be chosen in advance so it is important that the
number N is not divisible by any of them.
As an example, using a number of plants much smaller than the number used in an actual study, suppose that the
prime numbers chosen are 3, 5 and 7 and that the study can use no more than 25 plants. The multiples of
3 in this range are {3, 6, 9, 12, 15, 18, 21, 24}. The multiples of 5 are {5, 10, 15, 20, 25} and the
multiples of 7 are {7, 14, 21}. None of these numbers can be chosen for the number of plants in the study.
The numbers remaining, that could be chosen for N, are {1, 2, 4, 8, 11, 13, 16, 17, 19, 22, 23}.
So there are 11 possible candidates for the number of plants in the study.
For many studies it will be necessary to have significantly more than 3 different processes. Each new process
added will further restrict the number of possible values for the number of plants chosen for the study.
If there are still a large number of possibilities remaining, Bob can easily find an appropriate one by trial
and error. However, Bob, being a scientist, is naturally curious. He wonders just how many possible values for N
will remain, given a maximum value for the number of plants and the list of prime numbers associated with the
required processes. In the small example described above we have a maximum number of 25 plants and the prime
numbers {3, 5, 7}. The example shows that there are 11 possible values for N. Your task is to find this
number for a given maximum number of plants and the set of prime numbers associated with the processes.
Input and Answer
The first line of the problem will be a single integer K denoting the number of test cases.
Each of the following K lines will hold a series of numbers separated by spaces. The first of these numbers
is the maximum number of plants which can be used in the study. The remaining numbers on the same line are the
prime numbers associated with the processes. For each test case you must find the maximum number of different
integers which can be chosen for N, the number of plants in the study. Give these answers, separated by
spaces, as a single string.
Example:
input:
4
25 3 5 7
5741 37 97
194773 17 79 97
152295509 7 41 61 67 71
answer:
11 5528 179131 121659683