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 in the picture on the right: We want to know the minimum number of darts needed to obtain a score of q points on a prime dartboard of size n. Input The first line of the input contains an integer, t, indicating the number of prime dartboards. We can not be anything without playing to be. Jean-Paul Sartre 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 ≤ q ≤ 5000. Output 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. Sample Input 6 1 200 5 15 5 34 6 34 74 20 1000 Sample Output 200 3 6 4 2 16