SOLVE
LATER
Dragonite decided to go for hill climbing this weekend, but he doesn't have the map of all the hills. However he can make his own map. Since, well, he's a dragon, du'uh.
There are $$N$$ hills arranged on a line, each in the form of a vertical line segment with one endpoint on the ground. The hills are numbered with integers from $$1$$ to $$N$$ from left to right. The i_{th} hill has height h_{i}.
A beautiful set $$S$$ is set of hills such that for any h_{i}, h_{j} present in set $$S$$, (h_{i} * h_{j})%p!=1.
Note that here i can be equal to j. Here $$p$$ is any prime integer. To make the map, Dragonite needs maximum possible size of the beautiful set.
Note that two sets are considered different if they contain at least one point which is different. Two sets are considered same if they contain the same points.
Input format:
The first line of input contains two integers $$N$$, the number of hills and a prime number $$p$$. The next $$N$$ lines contains the height of the hills.
Output format:
Print the maximum possible size of the beautiful set possible.
Constraints:
2 ≤ $$N$$ ≤ 2 * 10^{5}
1 ≤ h_{i} ≤ 10^{18}
2 < $$p$$ < 10^{5}
References:
The two possible Beautiful Sets are {2,22} and {3,33}. Here 4 can't be any beautiful set because (4 * 4) % 5 =1 .Also 2 and 3 can't be in any beautiful set because (2 * 3) % 5 = 1. Also note that (2 * 22) % 5!=1 and (3 * 33) % 5!=1.