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.