A function $f$ is defined by the following recurrence relations:

$f(n+2) = 2*f(n+1) - f(n) + 2$, if $n$ is even

$f(n+2) = 3*f(n)$, if $n$ is odd

where $n>0$ and $f(1) = f(2) = 1$
You have to answer multiple queries. In each query, you are given two integers $L$ and $R$ and you are required to determine the value of $(f(L) + f(L+1) + ... + f(R-1) + f(R))\ modulo\ P$.

$P$ is fixed for all queries.

Input format

First line: Two integers $T\ (1 \le T \le 1000)$ and $P\ (1 \le P \le 10^9)$, where $T$ represents the number of queries
Each of the next $T$ lines: Two integers $L$ and $R\ (1 \le L \le R \le 10^{18})$

Output format

For each query, print the value of $(f(L) + f(L+1) + ... + f(R-1) + f(R))\ modulo\ P$ in a new line.