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.