Odd divisors

2.8

27 votes
Basic Programming
Problem

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 (T100) 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 (N1018, M109).

Output format

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

Sample Input
5
1 100
110 30
12345 100000007
10 28383
100 5
Sample Output
1
18
50804693
36
4
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

-

Editor Image

?