Recientemente se hizo un importante descubrimiento en IslaGrande: unos antiguos pergaminos que se rumoraba contenían la respuesta a muchas de las interrogantes de la humanidad. El primer pergamino estaba escrito en algún lenguaje caído en desuso y estaba firmado por la Bestia. Los demás pergaminos contenían tres números grandes seguidos de símbolos sin sentido.

Al poco tiempo, se terminó la traducción del primer pergamino, el cual describía un método de encriptación utilizado en los demás pergaminos. Para la época en la que los pergaminos fueron escritos, este método era demasiado avanzado. También describía que era posible calcular la clave de encriptación utilizando los tres números grandes (llamados ~a, b~ y ~n~) que se encontraban en cada pergamino.

Para calcular la clave, es necesario contar cuántos números en el intervalo cerrado ~[a, b]~, en su representación binaria tienen exactamente ~n~ bits encendidos (puestos a ~1~). Los arqueólogos de IslaGrande te dan esta importante tarea, por lo que debes hacer un programa para ellos que compute dicho cálculo.

Entrada

La primera línea de la entrada contiene un número entero ~n (1 < T \le 1000)~ que nos indica el número de casos de prueba. Cada caso contiene tres enteros ~a (1 \le a < 2^{31})~, ~b (a \le b < 2^{31})~ y ~n (1 \le n < 31)~.

Salida

Para cada caso, imprime la cantidad de números entre ~a~ y ~b~ (inclusive) que contengan exactamente ~n~ bits encendidos.

Ejemplo de Entrada

5
1 10 1
1 10 2
1 10 3
1 98305 3
41249 60398 12

Ejemplo de Salida

4
5
1
666
666