POLSKI SPOJ

Od ciągłego przesiadywania przy komputerze Bajtkowi strasznie pogorszył się wzrok. Nie obejdzie się bez okularów. Bajtek ich jednak bardzo nie lubi. Dlatego wszystko co tylko kojarzy się z okularami jest z zasady złe.

Ostatnio Bajtek zajmował się różnymi systemami liczbowymi. Wypisując różne liczby od razu wiedział, które nie będą dla niego dobre. Oczywiście wszystkie te, które w zapisie mają dwa zera obok siebie. I teraz się zastanawia: ile jest takich n-cyfrowych liczb w k-systemie liczbowym, które jest w stanie zaakceptować. Ponieważ może być ich bardzo dużo, wystarczy podać wynik modulo m.

Input

Na wejściu pojawi się liczba t (0 < t < 1001) określająca ilość zestawów testowych. Następnie t testów, każdy składający się z trzech liczb: n (0 < n < 10¹⁸), k (1 < k < 10¹⁸) i m (1 < m < 10¹⁸). n oznacza długość liczby, k - liczbę cyfr w badanym systemie liczbowym.

Output

Dla każdego testu należy podać odpowiedź na zadany problem modulo m.

Example

Input:
2
4 2 100
3 10 10000

Output:
5
891

Wyjaśnienie pierwszego przykładu:
Akceptowalne liczby to 1111, 1110, 1101, 1011 i 1010.