H - Span

Given an array of n integers X_1≤i≤n, the span S of X is an array of n integers with S_i being the maximum number of consecutive elements X_j immediately preceding X_i such that X_j≤X_i. In mathematical notation, elements of S are thus defined, 

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 X_1≤i≤n=(P_i mod m) where P_i 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	Sample Output
3 7 10 10 16 10 7	0 5 6