SP22270 PERIOD2 - Periodic function, trip 2

Milankovitch 周期理论展示了多个周期函数的累积效应。通过轨道强迫，我们可以研究地球过去的气候变化模式。  考虑定义域为 $\mathbb Z$，值域为 $\mathbb R$ 的**周期函数**，记它们构成的集合为 $V$。显然由于任意两个这样的函数周期的比值都是有理数，因此对于任意 $f,g\in V$ 有 $f+g\in V$，于是 $V$ 是一个向量空间。 以下我们会采用一种简化记号：我们用括号括起函数值的循环节代表函数，其中第一个数代表 $f(0)$。比如，若 $f=[2,4,7]$，那么有 $f(-1)=7,f(0)=2,f(1)=4,f(2)=7$，同理接下来 $f$ 的函数值就是 $2,4,7,2,4,7,2,4,7,\cdots$。$f$ 对应的 Python 代码为： ```python def f(x): return [2, 4, 7][x%3] # (with Python notations) # 2,4,7,2,4,7,2,4,7,2,4,7,2,4,7, ... ```

给定正整数 $N$。我们考虑在 $V$ 中任取一些周期不超过 $N$ 的函数，并计算这些函数的和 $f(x)$。可以证明存在一个正整数 $A$，使得无论我们怎么选取，$f$ 都是周期为 $A$ 的函数。你需要求出最小的满足条件的 $A$。 答案可能很大，你需要将输出对 $M$ 取模。

第一行一个正整数 $T$，代表数据组数。 接下来 $T$ 行，每行两个正整数 $N,M$，代表一组数据。

$T$ 行，每行一个整数，代表每组数据的答案。

### 数据范围 - $0< T