teddy online judge

31. Number of the Beast

Limite de tiempo : 1 seg.   Total runs : 371  Aceptados : 32

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 < 2³¹), b (a ≤ b < 2³¹) 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