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

Zadanie

Mając dane trzy liczby całkowite n, m oraz p, należy obliczyć sumy pierwszych, drugich, ..., m-tych potęg kolejnych liczb całkowitych od 0 do n i wyrazić je jako reszty z dzielenia ich przez p, gdzie p jest liczbą pierwszą. Innymi słowy, należy podać wartości następujących wyrażeń:

          (0 + 1 + 2 + ... + n) mod p
          (02 + 12 + 22 + ... + n2) mod p
          ....
          (0m + 1m + 2m + ... + nm) mod p

Specyfikacja wejścia

W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (1 ≤ D ≤ 30), oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. W pierwszym i jedynym wierszu każdego zestawu danych znajdują się trzy liczby całkowite oddzielone pojedynczymi spacjami n, m oraz p (0 ≤ n ≤ 1.000.000.000, 1 ≤ m ≤ 2.000, 1 ≤ p ≤ 60.000), opisane powyżej.

Specyfikacja wyjścia

Odpowiedź dla każdego zestawu należy poprzedzić linią postaci "Test x:", gdzie x to numer zestawu testowego (numerację zaczynamy od 1). W następnych m liniach należy wypisać po jednej liczbie całkowitej z przedziału od 0 do p-1, oznaczającej resztę z dzielenia sumy j-tych potęg kolejnych liczb od 0 do n przez p, dla kolejnych j z przedziału od 1 do m.

Przykład

2
3 2 11
2 3 2

Test 1:
6
3
Test 2:
1
1
1