Magic Doors

In front of little A there are 10¹⁰⁰⁰ doors numbered from 1 to 10¹⁰⁰⁰. Each door has a magic value equal to the number of 1's in its binary representation.

Little M, the keeper, challenges A: You will be given some intervals [l, r]. For each interval, compute two things modulo p:

• The sum of the magic values, i.e. \( S = \sum_{i=l}^{r} d_i \).
• The product of the magic values, i.e. \( P = \prod_{i=l}^{r} d_i \).

If you answer all queries correctly, you will obtain the treasures behind these doors.

Note: The magic value of a door numbered i is defined as \( d_i = \text{popcount}(i) \), i.e. the number of ones in the binary representation of i. Since the numbers can be huge, you are required to output the results modulo p.

Input/Output format details are given below.

inputFormat

The first line contains an integer T, the number of queries. Each of the next T lines contains three space‐separated values: l, r and p. Both l and r are positive integers (given in decimal) with 1 ≤ l ≤ r ≤ 10¹⁰⁰⁰, and p is a positive integer modulus.

outputFormat

For each query, output two space‐separated integers on a single line: the sum of magic values in the interval and the product of magic values in the interval, each taken modulo p.

sample

3
1 5 1000
2 7 1000
3 3 1000

7 4
11 24
2 2