E. Zebra-like Numberstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputWe 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$$$.InputEach 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}$$$).OutputFor each test case, output a single integer — the number of integers in $$$[l, r]$$$ with zebra value $$$k$$$.ExampleInput51 100 31 1 115 77 22 10 1001234567 123456789101112131 12Output13
1
3
0
4246658701
NoteIn 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.