Given an array of n integers X1≤i≤n, the span S of X is an array of n integers with Si being the maximum number of consecutive elements Xj immediately preceding Xi such that Xj ≤ Xi. In mathematical notation, elements of S are thus defined, Si = |Ai|, Ai ={j≤i|∀k(j≤k≤i)(Xk ≤Xi)}. As an example, the span of the array X = [40,2,10,50,30,15], is the array S = [1,1,2,4,1,1]. Now suppose, for given values of integers m and n, that X1≤i≤n = (Pi mod m) where Pi is the i-th prime number. We need to compute the sum-modulus-m of the elements of array S, span of X. If m = 10 and n = 7, we have X = [2,3,5,7,1,3,7] and S = [1,2,3,4,1,2,7]. The desired value is then, ((1 + 2 + 3 + 4 + 1 + 2 + 7) mod 10) = 0. Input The input file provides an integer T, on the first line, as the number of test-cases. For the next T lines, each line represents a test-case with two integers n and m both in the interval [1, 100000]. Output For each test-case print the sum of the elements of S mod m, as described above. Sample Input 3 7 10 10 16 10 7 Sample Output 0 5 6