CF2086E Zebra-like Numbers

We call a positive integer zebra-like if its binary representation has alternating bits up to the most significant bit, and the least significant bit is equal to $ 1 $ . For example, the numbers $ 1 $ , $ 5 $ , and $ 21 $ are zebra-like, as their binary representations $ 1 $ , $ 101 $ , and $ 10101 $ meet the requirements, while the number $ 10 $ is not zebra-like, as the least significant bit of its binary representation $ 1010 $ is $ 0 $ . We define the zebra value of a positive integer $ e $ as the minimum integer $ p $ such that $ e $ can be expressed as the sum of $ p $ zebra-like numbers (possibly the same, possibly different) Given three integers $ l $ , $ r $ , and $ k $ , calculate the number of integers $ x $ such that $ l \le x \le r $ and the zebra value of $ x $ equals $ k $ .

Each test consists of several test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The description of test cases follows. The only line of each test case contains three integers $ l $ , $ r $ ( $ 1 \le l \le r \le 10^{18} $ ) and $ k $ ( $ 1 \le k \le 10^{18} $ ).

For each test case, output a single integer — the number of integers in $ [l, r] $ with zebra value $ k $ .

In the first test case, there are $ 13 $ suitable numbers: $ 3, 7, 11, 15, 23, 27, 31, 43, 47, 63, 87, 91, 95 $ . Each of them can be represented as a sum of $ 3 $ zebra-like numbers.