You are given a positive integer $N$.$f(N)$ is the greatest odd divisor of $N$. 

Find the sum $(f(1) + f(2) + ... + f(N))\%M$.

Input format

• The first line of the input contains a single integer $T$ $(T ≤ 100)$ denoting the number of test cases. The description of $T$ test cases follows.
• The first line of each test case contains two integers $N$ and $M$ $(N ≤ 10^{18},\ M≤10^9)$.

Output format

For each value of $N$, print the value of $(f(1) + f(2) + ... + f(N))\%M$ in a separate line.