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;
vector<int> vec[100005];

int main(void)
{
	cin >> N >> M;
	int x;
	for(int i = 0; i < N; i++){
		cin >> x;
		vec[x % M].push_back(x);
	}
	for(int i = 0; i < M; i++) sort(vec[i].begin(), vec[i].end());
	
	int ans = 0;
	ans += vec[0].size() / 2;
	if(M % 2 == 0) ans += vec[M/2].size() / 2;
	
	for(int i = 1; i < (M+1)/2; i++){
		int lp = 0, up = 0, prev, cnt;
		
		prev = -1, cnt = 0;
		for(int j = 0; j < vec[i].size(); j++){
			if(prev == vec[i][j]) cnt++;
			else{
				lp += cnt / 2;
				cnt = 1;
			}
			prev = vec[i][j];
		}
		lp += cnt / 2;
		
		prev = -1, cnt = 0;
		for(int j = 0; j < vec[M-i].size(); j++){
			if(prev == vec[M-i][j]) cnt++;
			else{
				up += cnt / 2;
				cnt = 1;
			}
			prev = vec[M-i][j];
		}
		up += cnt / 2;
		
		int max_make = 0, make;
		for(int j = 0; j <= min(vec[i].size(), vec[M-i].size()); j++){
			make = min( ((int)vec[i].size() - j) / 2, lp ) + min( ((int)vec[M-i].size() - j) / 2, up ) + j;
			max_make = max(max_make, make);
		}
		ans += max_make;
	}
	
	cout << ans << endl;
	return 0;
}