We define a function $gay(i)$:
$$\displaystyle gay(i)=\left\{ \begin{array}{rcl} & 0, \quad& if \quad i = k*x*x, x > 1, k \geq 1 \\ & i * i ,\quad& else \end{array} \right. $$
Now your task is to calculate$$\displaystyle \sum_{num=1}^n (\sum_{i=1}^{num} gay(i)) \mod p $$
Multiple test cases. Please use EOF.
In each test case, there are two integers $n$, $p$, which are described above.
$1 \leq n \leq 10^{10},1 \leq p \leq 10^{11}$.
The number of test cases is no more than $100$.
For each test case print the answer in one line.
1 10 8 19230817
1 396