Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well.

Recently, Chef has moved to an evil land. In this land, there is only one bank, which offers $N$ savings plans (numbered $1$ through $N$).

Initially, Chef has $1$ coin in his account. He may choose bank plans for as long as he wishes, in any order; each plan may be chosen any number of times. For each valid $i$, whenever Chef chooses the $i$-th savings plan, the number of coins in his bank account gets multiplied by the *interest factor* $P_{i}$ of this plan (whenever he chooses this plan again, the number of coins is multiplied by $P_{i}$ again).

Since the bank in the evil land is evil, it always stores the number of coins in each account modulo $M$. Strangely, $M$ is a prime number.

Chef knows that he will *win the lottery* if the number of coins in his bank account becomes exactly $F$. The bank does not want Chef to win, so it decided to remove some of the $N$ savings plans.

You are the head of the evil bank. Therefore, you need to remove some (possibly none or all) plans in such a way that Chef cannot win the lottery. Find the minimum number of plans you must remove.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains three space-separated integers $N$, $M$ and $F$.
The second line contains $N$ space-separated integers $P_{1}, P_{2}, \ldots, P_{N}$.

------  Output ------
For each test case, print a single line containing one integer — the minimum number of plans to remove.

------  Constraints  ------
$1 ≤ T ≤ 50$
$1 ≤ N ≤ 10^{4}$
$1 ≤ M ≤ 2 \cdot 10^{5}$
$M$ is a prime number
$0 ≤ F < M$
$0 ≤ P_{i} < M$ for each valid $i$
$F \neq 1$

----- Sample Input 1 ------ 
4
2 5 3
2 4
2 3 2
1 2
7 7 0
4 1 3 2 0 6 5
10 11 2
9 1 10 4 5 8 2 3 6 0
----- Sample Output 1 ------ 
1
1
1
4
----- explanation 1 ------ 
Example case 1: Chef succeeds when he has $3$ coins in his bank account. He can achieve that by choosing plan $1$ and then plan $2$, since he would get $(2 \cdot 4) \% 5 = 3$ coins.

It is enough to delete plan $1$. Then, Chef cannot get $3$ coins, since he can only multiply the number of coins in his account by $4$.

Example case 3: Strangely, Chef succeeds when he has no coins in his bank account. The only way to achieve that is multiplying by $0$, so it is enough to delete plan $5$.

Difficulty: VERY_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
from copy import deepcopy
import os
import sys
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)
from typing import List

def getRoot(p: int) -> int:
	fact = []
	phi = p - 1
	n = phi
	for i in range(2, 1 + int(pow(n, 0.5))):
		if n % i == 0:
			fact.append(i)
			while n % i == 0:
				n /= i
	if n > 1:
		fact.append(n)
	for res in range(2, p + 1):
		ok = True
		for i in fact:
			ok = ok & (int(pow(res, int(phi // i), p)) != 1)
			if not ok:
				break
		if ok:
			return res
	return -1

def ninjaInEvilLand(n: int, m: int, f: int, arr: List[int]) -> int:
	revPower = [-1] * (m + 1)
	cnt = [0] * (m + 1)
	root = getRoot(m)
	curr = 1
	revPower[curr] = 0
	if f == 0:
		cnt0 = 0
		for a in arr:
			cnt0 += a == 0
		return cnt0
	j = 1
	while True:
		curr *= root
		curr %= m
		if revPower[curr] != -1:
			break
		revPower[curr] = j
		j += 1
	for i in range(n):
		arr[i] = revPower[arr[i]]
		arr[i] %= m
		cnt[arr[i]] += 1
	f = revPower[f]
	f %= m - 1
	ans = 0
	divisors = []
	for j in range(1, m):
		if (m - 1) % j == 0:
			divisors.append(j)
	for d in divisors:
		if f % d == 0:
			continue
		x = cnt[0]
		for i in range(d, m + 1, d):
			x += cnt[i]
		ans = max(ans, x)
	return n - ans

class Runner:

	def __init__(self):
		self.t = 0
		self.N = []
		self.M = []
		self.F = []
		self.ARR = []

	def takeInput(self):
		self.t = int(input().strip())
		for _ in range(self.t):
			(n, m, f) = map(int, input().split(' '))
			arri = list(map(int, input().split(' ')))
			self.N.append(n)
			self.M.append(m)
			self.F.append(f)
			self.ARR.append(arri)

	def execute(self):
		cpyN = deepcopy(self.N)
		cpyM = deepcopy(self.M)
		cpyF = deepcopy(self.F)
		cpyARR = deepcopy(self.ARR)
		for i in range(self.t):
			ans = ninjaInEvilLand(cpyN[i], cpyM[i], cpyF[i], cpyARR[i])
		del cpyN
		del cpyM
		del cpyF
		del cpyARR

	def executeAndPrintOutput(self):
		for i in range(self.t):
			ans = ninjaInEvilLand(self.N[i], self.M[i], self.F[i], self.ARR[i])
			print(ans)
runner = Runner()
runner.takeInput()
runner.executeAndPrintOutput()