Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3265
Strange Game

Time Limit: 3 Seconds      Memory Limit: 32768 KB

There is a strange game played on a special machine. The game has m prizes labeled from 0 to m-1. First, you are given n tickets, on which there is a number ai. For each time, you can put one ticket into the machine. By pressing the button on the machine you will get a number. You can press the button as many times as you like, but at least once. If you press k times, the number from the machine will be aik mod m, namely bi, and then you can take away the prize labeled bi as your trophy. Note that one ticket can only be used once, and same bi refers to same prize, which you can only take once.

Given n, m and ai, you need to find the maximum number of different prizes you can get.


The input contains no more than 30 cases. Each case has 2 lines. The first is two integers n, m (0 ≤ n ≤ 200, 0 < m ≤ 109). The second line contains n integers a0, a1, ..., an-1 (0 ≤ ai ≤ 109).

Proceed to the end of file.


For each case output a integer, indicating the maximum number of different prizes you can get.

Sample Input

2 2
1 2

Sample Output


Author: LI, Cheng
Source: ZOJ Monthly, November 2009
Submit    Status