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