Sparing w Programowaniu Zespołowym Politechnika Poznańska, 16.04.2004

Opis

Jeżeli przypatrzymy się liczbom binarnym, to zauważymy że różne liczby mają różną liczbę zer. Na przykład 10100b ma trzy zera. Interesują nas liczby, w których ilość zer jest wielokrotnością pewnej całkowitej dodatniej liczby k. Na przykład 100100b ma cztery zera, co jest wielokrotnością 4, 2 oraz 1. 111b ma zero zer, co jest wielokrotnością każdej całkowitej dodatniej liczby. Dla danych a, b podaj liczbę liczb przedziale [a, b], dla których liczba zer w rozwinięciu binarnym jest wielokrotnością k.

Specyfikacja wejścia

W pierwszym wierszu standardowego wejścia znajdzie się liczba d oznaczająca liczbę zestawów danych. Kolejno nastąpi d zestawów danych. Każdy składa się z trzech wierszy. W pierwszym wierszu znajdzie się liczba k (0 < k ≤ 10000). W dwóch kolejnych wierszach znajdują się liczby a i b (0 ≤ a ≤ b ≤ 2^10000). Podane są one w postaci binarnej, bez zbędnych zer wiodących. Znaczenie liczb a, b i k jest opisane w treści zadania.

Specyfikacja wyjścia

Dla każdego zestawu danych wypisz jedną liczbę oznaczającą liczbę szukanych liczb w danym przedziale. Podaj ją modulo 10^9.

Przykład

2
3
0
10
2
10
111

1
3