벽돌

게임을 끝낸 빅토르와 헥토르는 좀 더 생산적인 일, 바로 이웃집 별장 짓기를 돕기로 했습니다.

공사장에 방금 벽돌 $N$개가 도착했고, 두 사람은 이 벽돌을 여러 개의 더 작은 더미로 나누어야 합니다. 먼저 둘이 함께 전체 더미 하나를 두 개의 더 작은 더미로 나눕니다. 그다음부터는 각자 따로 작업하는데, 한 번의 작업은 기존 더미 하나를 골라 비어 있지 않은 두 개의 더 작은 더미로 나누는 것입니다.

두 사람이 잠시 쉬려고 손을 멈추었을 때, 다음 두 가지를 발견하고 놀랐습니다.

• 두 사람이 각자 혼자서 나눈 횟수가 서로 정확히 같았습니다.
• 완성된 모든 더미의 벽돌 개수가 소수였습니다.

두 사람이 만들 수 있는 서로 다른 최종 더미 구성은 몇 가지일까요? 어떤 더미 크기에 대해 한 구성이 다른 구성보다 그 크기의 더미를 더 많이 가지고 있으면 두 구성은 서로 다른 것으로 봅니다. 다시 말해, 하나의 구성은 더미 크기들의 다중집합으로 구별됩니다.

첫째 줄에 테스트 케이스의 수 $Z$ ($1 \le Z \le 10$)가 주어집니다.

둘째 줄에 나머지를 구할 정수 $M$ ($2 \le M \le 10^7$)이 주어집니다.

이어지는 $Z$개의 줄에는 각각 해당 케이스에서 배달된 벽돌의 개수 $N$ ($2 \le N \le 20000$)이 하나씩 주어집니다.

각 테스트 케이스마다, 벽돌 $N$개로 만들 수 있는 서로 다른 유효한 더미 구성의 수를 $M$으로 나눈 나머지를 한 줄에 하나씩 출력합니다.

$N = 5$일 때는 처음에 함께 더미를 $2$와 $3$(둘 다 소수)으로 나누고 이후 혼자서 나누는 작업을 전혀 하지 않는 방법이 유일하므로 답은 $1$입니다.

$N = 8$일 때는 두 가지 방법이 있습니다.

1. 더미를 $3$과 $5$(둘 다 소수)로 나누고 혼자서 나누는 작업을 하지 않습니다.
2. 더미를 $4$와 $4$로 나눈 뒤, 각자 $4$짜리 더미 하나를 $2$와 $2$로 나누어 최종적으로 $2, 2, 2, 2$가 됩니다.

따라서 답은 $2$입니다.