Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KBASENUM - Liczby do zaakceptowania

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 < 1018), k (1 < k < 1018) i m (1 < m < 1018). 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.


Dodane przez:Grzegorz Spryszyński
Data dodania:2015-07-15
Limit czasu wykonania programu:1s-2s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.