Fork me on GitHub

teddy online judge

teddy es un oso de peluche

31. Number of the Beast

Limite de tiempo : 1 seg.   Total runs : 357  Aceptados : 31

Woe to You Oh Earth and Sea
for the Devil sends the beast with wrath
because he knows the time is short
Let him who hath understanding
reckon the number of the beast
for it is a human number
— Iron Maiden, Number of the Beast


Recientemente se hizo un importante descubrimiento: 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.

Entrada

La primer línea de la entrada contiene un número entero n (1 < n ≤ 1000) que nos indica el número de casos de prueba. Cada caso contiene tres enteros a (1 ≤ a < 231), b (a ≤ b < 231) y n (1 ≤ n < 31).

Salida

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

Entrada de prueba

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

Salida de prueba

4
5
1
666
666


Luis Héctor Chávez Freire, 2008
1er Concurso Local de Programacion del Club de Progra

Hecho por Alan Gonzalez @_alanboy ; Concepto Luis Hector Chavez @lhchavez ; Infraestructura por Instituto Tecnologico de Celaya

contribuciones de los usuarios bajo la licencia cc-wiki con atribucion requerida