Назовем целое положительное число зебристым, если в его двоичной записи биты чередуются до самого старшего разряда, и самый младший бит равен $$$1$$$. Например, числа $$$1$$$, $$$5$$$ и $$$21$$$ — зебристые, так как их двоичные записи $$$1$$$, $$$101$$$ и $$$10101$$$ удовлетворяют требованиям, а число $$$10$$$ не является зебристым, так как младший бит его двоичной записи $$$1010$$$ равен $$$0$$$.
Назовем зебристостью целого положительного числа $$$e$$$ такое минимальное целое число $$$p$$$, что $$$e$$$ можно представить в виде суммы $$$p$$$ зебристых чисел (возможно, одинаковых, возможно, различных).
По заданным целым числам $$$l$$$, $$$r$$$ и $$$k$$$ посчитайте количество чисел $$$x$$$, таких, что $$$l \le x \le r$$$ и зебристость $$$x$$$ равна $$$k$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора данных содержит три целых числа $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$) и $$$k$$$ ($$$1 \le k \le 10^{18}$$$).
Для каждого набора входных данных выведите одно целое число — количество чисел из отрезка $$$[l, r]$$$ с зебристостью $$$k$$$.
51 100 31 1 115 77 22 10 1001234567 123456789101112131 12
13 1 3 0 4246658701
В первом наборе входных данных подходят $$$13$$$ чисел: $$$3, 7, 11, 15, 23, 27, 31, 43, 47, 63, 87, 91, 95$$$.
Каждое из них можно представить в виде суммы $$$3$$$ зебристых чисел.
