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⁵
1 ≤ h_i ≤ 10¹⁸
2 < p < 10⁵

References: