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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, A[100009], par[100009]; vector<int>X[100009];

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		X[A[i] % M].push_back(A[i]);
	}
	for (int i = 0; i < M; i++) {
		sort(X[i].begin(), X[i].end());
		for (int j = 0; j < (int)X[i].size() - 1; j++) {
			if (X[i][j] == X[i][j + 1]) { par[i]++; j++; }
		}
	}
	vector<int>A; int sum = 0;
	for (int i = 0; i < M; i++) {
		if (i%M > (M - i) % M) continue;
		if (i%M == (M - i) % M) {
			A.push_back(i);
			continue;
		}
		int Z = min(X[i].size(), X[M - i].size());
		sum += Z;
		sum += min(par[i], ((int)X[i].size() - Z) / 2);
		sum += min(par[M - i], ((int)X[M - i].size() - Z) / 2);
	}
	for (int i = 0; i < A.size(); i++) {
		sum += X[A[i]].size() / 2;
	}
	cout << sum << endl;
	return 0;
}