Takahashi is playing with N cards.

The i-th card has an integer X_i on it.

Takahashi is trying to create as many pairs of cards as possible satisfying one of the following conditions:

* The integers on the two cards are the same.
* The sum of the integers on the two cards is a multiple of M.



Find the maximum number of pairs that can be created.

Note that a card cannot be used in more than one pair.

Constraints

* 2≦N≦10^5
* 1≦M≦10^5
* 1≦X_i≦10^5

Input

The input is given from Standard Input in the following format:


N M
X_1 X_2 ... X_N


Output

Print the maximum number of pairs that can be created.

Examples

Input

7 5
3 1 4 1 5 9 2


Output

3


Input

15 10
1 5 6 10 11 11 11 20 21 25 25 26 99 99 99


Output

6
#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,t) for(int i = s; i <= t; ++ i)
const int MaxN = 100050;

int n, m, x, ans;
int cnt[MaxN], hs[MaxN], pa[MaxN];

int main()
{
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%d",&x), cnt[x%m] ++, hs[x] ++;
    ans += cnt[0]/2, cnt[0] = 0;
    if(m%2==0) ans += cnt[m/2]/2, cnt[m/2] = 0;
    rep(i,1,m/2-(m%2==0))
        if(cnt[i] && cnt[m-i])
        {
            if(cnt[i] < cnt[m-i])
            {
                ans += cnt[i];
                cnt[m-i] -= cnt[i]; cnt[i] = 0;
            }
            else
            {
                ans += cnt[m-i];
                cnt[i] -= cnt[m-i]; cnt[m-i] = 0;
            }
        }
    rep(i,0,m-1) for(int j = i; j <= MaxN-50; j += m)
        if(cnt[i] < 2) break;
        else {ans += min(cnt[i],hs[j])/2; cnt[i] -= min(cnt[i],hs[j])/2*2;}
    cout << ans;
    return 0;
}
