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 ith hill has height hi.
A beautiful set S is set of hills such that for any hi, hj present in set S, (hi * hj)%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 * 105
1 ≤ hi ≤ 1018
2 < p < 105
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.
