Монокарп недавно изучил двоичную систему счисления. Теперь он умеет переводить целые положительные числа из десятичной системы счисления в двоичную. После перевода он записывает число в двоичной системе счисления, начиная со старшего значимого разряда, равного $$$1$$$, то есть записывает числа без лидирующих нулей.
Монокарпу стало интересно, сколько целых десятичных чисел в промежутке от $$$a$$$ до $$$b$$$ включительно в своей двоичной записи имеют ровно $$$k$$$ разрядов, равных $$$1$$$.
Перед вами стоит задача помочь Монокарпу ответить на этот вопрос.
В первой строке следует одно целое число $$$t$$$ ($$$1 \le t \le 1\,000$$$) — количество наборов входных данных.
В единственной строке каждого набора входных данных следуют три целых числа $$$a$$$, $$$b$$$ и $$$k$$$ ($$$1 \le a \le b \le 10^{9}$$$, $$$1 \le k \le 30$$$) — левая и правая границы промежутка, а также количество разрядов, которые должны быть равны $$$1$$$ в двоичной записи числа.
Для каждого набора входных данных выведите в отдельную строку одно целое число — количество целых чисел в промежутке от $$$a$$$ до $$$b$$$ включительно, которые в своей двоичной записи имеют ровно $$$k$$$ разрядов, равных $$$1$$$.
34 15 263 63 61 1000000000 21
5110722629
В первом наборе входных данных в промежутке $$$[4, 15]$$$ существует $$$5$$$ чисел, в двоичной записи которых встречается ровно $$$2$$$ разряда, равных $$$1$$$: $$$5_{10} = 101_{2}$$$, $$$6_{10} = 110_{2}$$$, $$$9_{10} = 1001_{2}$$$, $$$10_{10} = 1010_2$$$ и $$$12_{10} = 1100_{2}$$$.
Во втором наборе входных данных в промежутке $$$[63, 63]$$$ есть ровно одно целое число $$$63_{10} = 111111_{2}$$$, в записи которого $$$6$$$ разрядов, равных $$$1$$$, поэтому ответ на этот набор входных данных равен $$$1$$$.
