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 <cstdio>
#include <algorithm>
#include <vector>
#include <map>

int main() {
  int N, M;
  scanf("%d %d", &N, &M);

  std::vector<std::map<int, int>> A(M);
  std::vector<int> B(M);
  for (int i=0; i<N; ++i) {
    int X;
    scanf("%d", &X);
    ++A[X%M][X];
    ++B[X%M];
  }

  int res=0;
  for (int i=0; i<=M/2; ++i) {
    if (i == M-i || i == 0) {
      res += B[i]/2;
      continue;
    }

    int cur = std::min(B[i], B[M-i]);
    res += cur;

    if (B[i] == B[M-i])
      continue;

    int k=i;
    if (B[i] < B[M-i])
      k = M-i;

    //int rest=B[k]-B[i^(M-i)^k];
    int rest=cur;
    int pairs=0;
    for (std::pair<const int, int> &p: A[k]) {
      if (rest > 0 && p.second % 2) {
        --p.second;
        --rest;
      }

      pairs += p.second / 2;
      //fprintf(stderr, "%d: %d\n", p.first, p.second/2);
    }

    while (rest > 0) {
      --pairs;
      rest -= 2;
    }

    res += pairs;
  }

  printf("%d\n", res);
  return 0;
}
