CERI2018B - A function table


Let $f(n) = 12345n^2 + 6789n + 1337$

Input

The first line of the input consist of a single integer number t which determines the number of tests.

In each of next t lines there is two integer numbers n and m.

Constraints

  • 0 < t ≤ 100 000
  • 0 ≤ n ≤ 50 000 000
  • 2 ≤ m ≤ 2 000 000 000

Output

Print the result of $f(n)$ modulo $m$.

Example

Input:
4
0 10000
1 10000
2 10000
1000 1000000007
Output:
1337
471
4295
351790253


Added by:Francky
Date:2018-05-02
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All