Given \(Q\) queries of type \(L \ R \ X\), find the count of integers in range \([L, R]\) such that their \(X^{th}\) bit (1-indexed) is \(ON\) from the LSB (least significant bit) side.

Input Format:

• First line contains an integer \(Q\), denoting the number of queries.
• Next \(Q\) lines contains three space-separated integres \(L \ R \ X\).

Output Format:

For every query, print the number of integers in \([L, R]\) which satisfy the above condition.

Constraints:

\(1 \le Q \le 10^5 \\ 1 \le L \le R \le 10^5 \\ 1 \leq X \leq 20\)