시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 5 2 1 100.000%

문제

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 <= <= 20000 ).

출력

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

예제 입력 1

2
1000
5
8

예제 출력 1

1
2

힌트

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.

출처

Contest > Spot > HotSpot 2010 2-4번