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.