Milankovitch's cycle theory is an example with cumulative effect of several periodic functions.
We can study past climatic patterns on Earth through orbital forcing.

Let us consider periodic functions from Z to R.

	def f(x): return [4, -6, 7][x%3] # (with Python notations)
	# 4, -6, 7, 4, -6, 7, 4, -6, 7, 4, -6, 7, 4, -6, 7, ...

For example, f is a 3-periodic function, with f(0) = f(3) = f(6) = f(9) = 4.
With a simplified notation we will denote f as [4, -6, 7].
For two periodic functions (with integral period), the quotient of periods will be rational, in that case it can be shown that the sum of the functions is also a periodic function.
Thus, the set of all such functions is a vector space over R.

Our interest, in this problem, will be the smallest common period of sums of periodic functions whose period is an integer, bounded by some N.

Input

The first line contains an integer T, the number of test cases.
On the next T lines, you will be given two integers N and M.
Consider the family of any finite sum of ( n-periodic functions with n in [1..N] ).
All those functions share a common smallest period.

Output

Print the smallest common period of that family. As the answer can get very big, simply output it modulo M.

Example

Input:
3
2 10
3 100
4 7

Output:
2
6
5

Explanation

The first case is trivial.
For the second case, for example if f = [0] + [5, π] + [0, -e , 1] then f can be written as [5, π-e, 6, π, 5-e, π+1] and is 6-periodic ; 6 is smallest common period for any sum of n-periodic function when n is bounded by 3.
For the third case, 12%7 is equal to 5.

Constraints

0 < T < 10^3
0 < N < 10^7
1 < M < 10^9

Uniform random input, one input file.

Information

Constraints allow my optimized Python code to get AC in 12s, and a poor C code in 4s. The curious fact is that on my hardware the corresponding times are quite the same, and I've set the constraints with that in mind... curious for me.

Edit 2017-02-11 : with compiler changes, now the two times are similar 3.5s (poor.c) ; 3.57s (good.py). The new TL is set at 7s. It allows JAVA too.