E - Prime Darts |
We can not be anything without playing to be.
Jean-Paul Sartre
A dartboard manufacturer wants to revolutionize the game of darts, creating a prime dartboard for math geeks. He has designed several boards with different numbers of areas, so that a board with n areas has the following scores: the first area is worth 1 point, the remaining n-1 areas have a value corresponding to the first n-1 prime numbers.
For example, a prime dartboard with 20 areas could be as follows:
We want to know the minimum number of darts needed to obtain a score of q points on a prime dartboard of size n.
The first line of the input contains an integer, t, indicating the number of prime dartboards.
For each case, there is a line with two numbers separated by a space. The first one, n, represents the number of areas of the board, with 1 ≤ n ≤ 100, and the second number, q, indicates the score we have to get, with 1 ≤ k ≤ 5000.
For each test case, the output should consist of one line showing the minimum number of darts needed to obtain a q points on a prime dartboard of size n.
6 1 200 5 15 5 34 6 34 7 4 20 1000
200 3 6 4 2 16