8821번 - Cegły 다국어

Wiktor z Hektorem, skończywszy Rozgrywkę, zabrali się do nieco bardziej produktywnego zajęcia - pomocy przy budowie domku letniskowego ich sąsiada.

Na teren budowy właśnie przywieziono dostawę N cegieł, które chłopcy mają podzielić na mniejsze stosiki. Obaj zabrali się do pracy, dzieląc najpierw wspólnie cały stos na dwa mniejsze. Następnie każdy z nich zabrał się do samodzielnych podziałów, każdorazowo dzieląc jeden ze stosów na dwa mniejsze.

Kiedy chłopcy zmęczyli się pracą i zrobili sobie przerwę, ze zdziwieniem zauważyli, że:

• Każdy z nich wykonał tyle samo samodzielnych podziałów.
• Liczba cegieł w każdym z powstałych stosów jest liczbą pierwszą.

Ile takich różnych podziałów na stosy mogli osiągnąć? Dwa podziały uważamy za różne, jeśli w jednym z nich jest więcej stosów pewnej wielkości niż w drugim.

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ).

W drugiej linii jest jedna liczba naturalna M  (2 <= M <= 10000000 ).

W kolejnych Z liniach znajdują się opisy zestawów. Każdy z nich składa się z jednej liczby naturalnej N ( 2 <= N <= 20000 ).

Jedna liczba całkowita - reszta z dzielenia ilości możliwych podziałów osiągniętych przez Wiktora i Hektora przez liczbę M.

W pierwszym przypadku chłopcy podzielili stos na dwa mniejsze o wielkości 2, 3 i nie wykonywali samodzielnych podziałów. W drugim przypadku mogli uzyskać dwa różne podziały:

1. podzielili stos na 3, 5 i nie wykonywali samodzielnych podziałów,
2. podzielili stos na 4, 4, po czym każdy podzielił stos 4 na dwa stosiki wielkości 2. Otrzymali więc stosiki 2, 2, 2, 2.