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$$$.

Input

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}$$$).

Output

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

Note

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.

Zebra-like Numbers

Examples