Salazar Slytherin's Locket
Contest: Manthan, Codefest 17
Difficulty rating: 2200
Tags: bitmasks, dp

Harry came to know from Dumbledore that Salazar Slytherin's locket is a horcrux. This locket was present earlier at 12 Grimmauld Place, the home of Sirius Black's mother. It was stolen from there and is now present in the Ministry of Magic in the office of Dolorous Umbridge, Harry's former Defense Against the Dark Arts teacher.

Harry, Ron and Hermione are infiltrating the Ministry. Upon reaching Umbridge's office, they observed a code lock with a puzzle asking them to calculate count of magic numbers between two integers l and r (both inclusive).

Harry remembered from his detention time with Umbridge that she defined a magic number as a number which when converted to a given base b, all the digits from 0 to b - 1 appear even number of times in its representation without any leading zeros.

You have to answer q queries to unlock the office. Each query has three integers bi, li and ri, the base and the range for which you have to find the count of magic numbers.

Input format:
First line of input contains q (1 ≤ q ≤ 105) — number of queries.

Each of the next q lines contain three space separated integers bi, li, ri (2 ≤ bi ≤ 10, 1 ≤ li ≤ ri ≤ 1018).

Output format:
You have to output q lines, each containing a single integer, the answer to the corresponding query.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In sample test case 1, for first query, when we convert numbers 4 to 9 into base 2, we get:

- 4 = 1002,
- 5 = 1012,
- 6 = 1102,
- 7 = 1112,
- 8 = 10002,
- 9 = 10012.

Out of these, only base 2 representation of 9 has even number of 1 and 0. Thus, the answer is 1.

Example input:
2
2 4 9
3 1 10

Example output:
1
2

Example input:
2
2 1 100
5 1 100

Example output:
21
4

Editorial:
This problem can be solved using precomputation of dp table dp[base][mask][len]. This stores the number of integers in base b and length len that forms the given mask in their representation. The mask is defined as having i - th bit as 1, if the digit i - 1 occurs odd number of times in the representation.
Using this precomputed dp array, we can easily calculate the answer for the queries, by converting l - 1 and r to the given base b, then adding the total integers less than equal to r with mask = 0 and subtracting those less than l with mask = 0.
Now, to find the number of integers less than equal to l - 1 with mask = 0, we first add all the integers with mask = 0 who have length less than length of l - 1 in base b representation. If length of l - 1 in base b is lb, this value can be calculated as $$\sum_{1 \leq i < l_b} dp[b][0][i] - dp[b][1][i-1]$$. The second term is subtracted to take into account the trailing zeros.
Now, we need to calculate the number of integers with length = lb and value ≤ l - 1 and mask = 0. Let the number l - 1 in base b representation be l0, l1... llb. Then, if we fix the first digit of our answer, x from 0 to l0 - 1, we can simply calculate the mask for remaining digits we need as 2x and thus adding dp[b][2x][len - 1] to answer.
Now, if we fix the first digit as l0 only, we can simply perform the same operation for the second digit, selecting value of second digit, y from 0 to l1 - 1, and thus adding $$dp[b][len-2][2^x \oplus 2^y]$$ to answer. And, we can move forward to rest of the digits in the same way.
The overall complexity of the solution will be $$O(b \cdot 2^b \cdot \log_b{10^{18}} + q \cdot b \cdot \log_b{r})$$