PERIOD2 - Periodic function, trip 2

no tags 

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.

Milankovitch cycles - image

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.


hide comments
Gonzalo Ciruelos: 2015-02-18 00:05:50

Are the test cases generated uniformly randomly? The program runs in 5-6s on my pc with 1000 uniformly generated pairs (10^7 and 10^9 limits), but my submissions get TLE.

(Francky) => As stated in description, input is uniform randomly chosen.

Last edit: 2015-02-18 00:51:42
FoolForCS: 2015-01-14 21:58:53

Nice problem. :)

wisfaq: 2015-01-03 21:07:35

Some comments on the English:

Milankovitch cycles theory -->Milankovitch's cycle theory

the quotient of periods will be rationnal --> the quotient of periods will be rational

We'll use [4, -6, 7] as f with simplified notations -->
With a simplified notation we will denote f as [4, -6, 7].

Consider the familly of any--> Consider the family of any

--francky--> Many thanks. Done.
@all : don't hesitate to do the same in any problem where it could add a benefit.

Last edit: 2015-01-03 21:32:56
Francky: 2014-12-30 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.
==
This second trip will be an easy one, except for Python user : who will take the glove ?
Have fun ;-)


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