PERIOD2  Periodic function, trip 2
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 3periodic 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 ( nperiodic 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, π, 5e, π+1] and is 6periodic ; 6 is smallest common period for any sum of nperiodic 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 20170211 : 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.
hide comments
Gonzalo Ciruelos:
20150218 00:05:50
Are the test cases generated uniformly randomly? The program runs in 56s on my pc with 1000 uniformly generated pairs (10^7 and 10^9 limits), but my submissions get TLE.


FoolForCS:
20150114 21:58:53
Nice problem. :) 

wisfaq:
20150103 21:07:35
Some comments on the English:


Francky:
20141230 22:45:37
As I consider my English very poor, please share if you see any improvement in writing. Without answer I'll delete this message.

Added by:  Francky 
Date:  20141229 
Time limit:  7s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 