Given a set of distinct integers, print the size of a maximal subset of $S$ where the sum of any $2$ numbers in $\text{S'}$ is not evenly divisible by $k$.

Example 

$S=[19,10,12,10,24,25,22]$ $k=4$

One of the arrays that can be created is $S'[0]=[10,12,25]$.  Another is $S'[1]=[19,22,24]$.  After testing all permutations, the maximum length solution array has $3$ elements.  

Function Description  

Complete the nonDivisibleSubset function in the editor below.  

nonDivisibleSubset has the following parameter(s):  

int S[n]: an array of integers  
int k: the divisor  

Returns   

int: the length of the longest subset of $S$ meeting the criteria  

Input Format

The first line contains $2$ space-separated integers, $n$ and $k$, the number of values in $S$ and the non factor. 

The second line contains $n$ space-separated integers, each an $S[i]$, the unique values of the set.

Constraints

$1 \leq n \leq 10^5$
$1 \le k \le100$
$1\leq S[i]\leq10^{9}$
All of the given numbers are distinct.

Sample Input
STDIN    Function
-----    --------
4 3      S[] size n = 4, k = 3
1 7 2 4  S = [1, 7, 2, 4]

Sample Output
3

Explanation

The sums of all permutations of two elements from $S=\{1,7,2,4\}$ are:

1 + 7 = 8
1 + 2 = 3
1 + 4 = 5
7 + 2 = 9
7 + 4 = 11
2 + 4 = 6

Only $S'=\{1,7,4\}$ will not ever sum to a multiple of $k=3$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Implementation


Solutions:
read = lambda : map(int, input().split())
(n, k) = read()
a = list(read())
cnt = [0] * k
for x in a:
	cnt[x % k] += 1
ans = min(cnt[0], 1)
for rem in range(1, (k + 1) // 2):
	ans += max(cnt[rem], cnt[k - rem])
if k % 2 == 0:
	ans += min(cnt[k // 2], 1)
print(ans)


def main():
	(n, k) = [int(fld) for fld in input().split()]
	a = [int(fld) for fld in input().split()]
	assert n == len(a)
	modclass = [0] * k
	for elt in a:
		modclass[elt % k] += 1
	ans = sum((max(modclass[i], modclass[k - i]) for i in range(1, (k + 1) // 2)))
	if modclass[0] != 0:
		ans += 1
	if k % 2 == 0 and modclass[k // 2] != 0:
		ans += 1
	print(ans)
main()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
cnt = [0] * k
for i in range(n):
	cnt[a[i] % k] += 1
ans = min(cnt[0], 1)
if k % 2 == 0:
	ans += min(cnt[k // 2], 1)
for i in range(1, (k + 1) // 2):
	ans += max(cnt[i], cnt[k - i])
print(ans)


(n, k) = [int(temp) for temp in input().strip().split()]
s = [int(temp) % k for temp in input().strip().split()]
remainder = [0] * k
for x in s:
	remainder[x] += 1
ans = 0
for i in range(1, k // 2):
	ans += max(remainder[i], remainder[k - i])
if remainder[0] > 0:
	ans += 1
if k % 2 == 0 and remainder[k // 2] > 0:
	ans += 1
elif k % 2 == 1 and k > 1:
	ans += max(remainder[k // 2], remainder[k - k // 2])
print(ans)


(n, k) = map(int, input().split())
table = [0] * k
for v in map(int, input().split()):
	table[v % k] += 1
ans = min(1, table[0])
if not k & 1:
	ans += min(1, table[k // 2])
for i in range(1, (k + 1) // 2):
	ans += max(table[i], table[k - i])
print(ans)


(n, k) = (int(x) for x in input().split())
a = tuple((int(x) for x in input().split()))
d = {}
for e in a:
	key = e % k
	if key in d:
		d[key] += 1
	else:
		d[key] = 1
m = 0
if 0 in d:
	m += 1
if k % 2 == 0:
	stop = k // 2
	if k // 2 in d:
		m += 1
else:
	stop = k // 2 + 1
for i in range(1, stop):
	if i in d:
		a = d[i]
	else:
		a = 0
	if k - i in d:
		b = d[k - i]
	else:
		b = 0
	m += max(a, b)
print(m)


from collections import defaultdict
(n, k) = [int(item) for item in input().strip().split()]
S = [int(item) for item in input().strip().split()]
mods = [item % k for item in S]
freqs = defaultdict(int)
for elem in mods:
	freqs[elem] += 1
total = 0
for (key, val) in freqs.items():
	if val == 0:
		continue
	if key == 0:
		total += 1
	elif k - key == key:
		total += 1
	elif key > k - key:
		if k - key in freqs:
			total += max([val, freqs[k - key]])
		else:
			total += val
	elif key < k - key:
		if k - key not in freqs:
			total += val
print(total)


from collections import Counter
(n, k) = map(int, input().split())
a = map(int, input().split())
ctr = Counter((i % k for i in a))
print(min(ctr[0], 1) + (k % 2 == 0 and min(ctr[k // 2], 1)) + sum((max(ctr[c], ctr[k - c]) for c in range(1, (k + 1) // 2))))


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
count = [0] * k
j = k - 1
ans = 0
for i in range(n):
	count[arr[i] % k] += 1
for i in range(1, k):
	ans += max(count[i], count[j])
	j -= 1
	if i >= j:
		break
if count[0] > 0:
	ans += 1
if k & 1 == 1:
	print(ans)
else:
	if count[k // 2] > 1:
		ans -= count[k // 2]
		ans += 1
	print(ans)


def main():
	(n, k) = map(int, input().split())
	counter = [0] * k
	for x in map(int, input().split()):
		counter[x % k] += 1
	subsetsize = 0
	for (x, y) in zip(range(1, k // 2 + 1), range(k - 1, k // 2, -1)):
		subsetsize += max(counter[x], counter[y])
	if k % 2 == 0:
		subsetsize += counter[k // 2] != 0
	subsetsize += counter[0] != 0
	print(subsetsize)
main()


(n, k) = map(int, input().split())
modk = [0 for _ in range(k)]
for el in map(int, input().split()):
	modk[el % k] += 1
res = 0
for i in range(1, k // 2 + 1):
	if k % 2 == 0 and i == k // 2:
		continue
	res += max(modk[i], modk[k - i])
if modk[0]:
	res += 1
if k % 2 == 0 and modk[k // 2]:
	res += 1
print(res)


import math
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
total = 0
remainders = {i: 0 for i in range(k)}
for x in a:
	remainders[x % k] += 1
if k % 2 == 0:
	for i in range(1, k // 2):
		total += max(remainders[i], remainders[k - i])
	if remainders[k // 2] > 0:
		total += 1
else:
	for i in range(1, k // 2 + 1):
		total += max(remainders[i], remainders[k - i])
if remainders[0] > 0:
	total += 1
if total == 0:
	total = 1
print(total)


(n, k) = map(int, input().split())
A_residue = [int(x) % k for x in input().split()]
c = [0] * k
for a in A_residue:
	c[a] += 1
result = 0
if c[0]:
	result += 1
if not k & 1 and c[k >> 1]:
	result += 1
for i in range(1, k + 1 >> 1):
	result += max(c[i], c[k - i])
print(result)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
a = [int(a_temp) for a_temp in input().strip().split(' ')]
k_rem = [0 for i in range(k)]
for i in a:
	k_rem[i % k] += 1
count = 0
if k % 2 == 0:
	for i in range(1, k // 2):
		count += max(k_rem[i], k_rem[k - i])
	if k_rem[0] > 0:
		count += 1
	if k_rem[k // 2] > 0:
		count += 1
elif k % 2 == 1:
	for i in range(1, (k + 1) // 2):
		count += max(k_rem[i], k_rem[k - i])
	if k_rem[0] > 0:
		count += 1
print(count)


(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
l = [0 for i in range(k)]
for i in a:
	l[i % k] += 1
ans = 0
for i in range(1, (k - 1) // 2 + 1):
	if l[i] > l[k - i]:
		ans += l[i]
	else:
		ans += l[k - i]
if l[0] > 0:
	ans += 1
if k % 2 == 0 and l[k // 2] > 0:
	ans += 1
print(ans)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
a = [int(a_temp) for a_temp in input().strip().split(' ')]
amodk = {}
for i in range(k):
	amodk[i] = 0
exist = False
for i in a:
	amodk[i % k] += 1
count = 0
for j in range(1, k // 2 + 1):
	count += max(amodk[j], amodk[k - j])
if amodk[0] > 0:
	count += 1
if k % 2 == 0:
	if amodk[k // 2] > 1:
		count -= amodk[k // 2]
		count += 1
print(count)


import math
(n, k) = [int(x) for x in input().strip().split(' ')]
arr = [int(x) % k for x in input().strip().split(' ')]
arrcount = [arr.count(x) for x in range(k)]
count = 0
count += min(1, arrcount[0])
if k % 2 == 0:
	count += min(1, arrcount[k // 2])
for i in range(1, math.ceil(k / 2)):
	count += max(arrcount[i], arrcount[k - i])
print(count)


from fractions import gcd
(n, k) = [int(i) for i in input().split()]
S = [int(i) for i in input().split()]
C = [0] * k
for i in range(n):
	C[S[i] % k] += 1
count = 0
if C[0] > 0:
	count += 1
if k % 2 == 0:
	if C[k // 2] > 0:
		count += 1
	for i in range(1, k // 2):
		c1 = C[i]
		c2 = C[k - i]
		count += max(c1, c2)
else:
	for i in range(1, k // 2 + 1):
		c1 = C[i]
		c2 = C[k - i]
		count += max(c1, c2)
print(int(count))


import math
(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
hlp = [0 for x in range(k)]
for i in range(n):
	val = a[i] % k
	hlp[val] += 1
cnt = min(1, hlp[0])
for i in range(1, math.ceil(k / 2)):
	cnt += max(hlp[i], hlp[k - i])
if k % 2 == 0 and hlp[k // 2] > 0:
	cnt += 1
print(cnt)


(n, k) = [int(x) for x in input().split()]
s = [int(x) for x in input().split()]
L = [0] * k
for num in s:
	L[num % k] += 1
if L[0] != 0:
	size = 1
else:
	size = 0
for i in range(1, k // 2 + 1):
	if i == k - i and L[i] != 0:
		size += 1
	elif L[i] >= L[k - i]:
		size += L[i]
	else:
		size += L[k - i]
print(size)


[n, k] = [int(a) for a in input().split()]
s = [int(a) for a in input().split()]
s = set(s)
modclass = [0] * k
count = 0
for i in s:
	modclass[i % k] += 1
if k % 2 == 0:
	upperBound = k // 2
else:
	upperBound = k // 2 + 1
for i in range(1, upperBound):
	if modclass[i] > modclass[k - i]:
		count += modclass[i]
	else:
		count += modclass[k - i]
if modclass[0] > 0:
	count += 1
if k % 2 == 0 and modclass[k // 2] > 0:
	count += 1
print(count)


(N, K) = [int(x) for x in input().strip().split()]
A = [int(x) % K for x in input().strip().split()]
residues = [0] * K
for a in A:
	residues[a] += 1
acc = 0
for residue in range(1, (K + 1) // 2):
	acc += max(residues[residue], residues[K - residue])
acc += min(1, residues[0])
if K % 2 == 0:
	acc += min(1, residues[K // 2])
print(acc)


(n, k) = tuple(map(int, input().split()))
vals = list(map(int, input().split()))
mod_dict = {}
for item in vals:
	mod = item % k
	if mod not in mod_dict:
		mod_dict[mod] = 0
	mod_dict[mod] += 1
mods = sorted(mod_dict.items(), key=lambda x: x[1], reverse=True)
total = 0
blacklist = set()
for pair in mods:
	mod = pair[0]
	val = pair[1]
	if mod in blacklist:
		continue
	if mod == k / 2 or mod == 0:
		total += 1
	else:
		total += val
		blacklist.add(k - mod)
print(total)


from math import ceil
(N, K) = [int(n) for n in input().split()]
nums = [int(n) % K for n in input().split()]
dic = {n: 0 for n in range(K)}
for num in nums:
	dic[num] += 1
tot = 0
if dic[0] > 0:
	tot += 1
for n in range(1, ceil(K / 2)):
	tot += max(dic[n], dic[K - n])
if K % 2 is 0 and dic[K / 2] > 0:
	tot += 1
print(tot)


(n, k) = map(int, input().strip().split())
a = map(int, input().strip().split())
moddata = [0] * k
for x in a:
	moddata[x % k] += 1
workingsum = sum(moddata[1:])
workingsum -= moddata[k // 2] if k % 2 == 0 else 0
testdata = moddata[1:] if k % 2 else moddata[1:k // 2] + moddata[k // 2 + 1:]
for i in range(len(testdata) // 2):
	if testdata[i] < testdata[-(i + 1)]:
		workingsum -= testdata[i]
	else:
		workingsum -= testdata[-(i + 1)]
workingsum += 1 if moddata[0] else 0
workingsum += 1 if k % 2 == 0 and moddata[k // 2] else 0
print(workingsum)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
r = [0 for i in range(k)]
for i in a:
	r[i % k] += 1
count = 1 if r[0] else 0
for i in range(1, k):
	j = k - i
	if i == j:
		count += 1
		break
	elif j < i:
		break
	else:
		count += max(r[i], r[j])
print(count)


(n, k) = map(int, input().strip().split(' '))
S = list(map(int, input().strip().split(' ')))
remainders = {r: 0 for r in range(k)}
for s in S:
	remainders[s % k] += 1
remainders = [(r, remainders[r]) for r in remainders]
remainders.sort(key=lambda x: x[1], reverse=True)
max_num_elems = 0
done = []
for (r, num) in remainders:
	if k - r in done:
		continue
	if r == 0 and num > 0:
		max_num_elems += 1
		continue
	if 2 * r == k and num > 0:
		max_num_elems += 1
		continue
	max_num_elems += num
	done.append(r)
print(max_num_elems)


(n, k) = map(int, input().strip().split())
D = [0] * k
for i in input().strip().split():
	D[int(i) % k] += 1
size = min(1, D[0])
i = 1
while i < k - i:
	size += max(D[i], D[k - i])
	i += 1
if i == k - i:
	size += min(1, D[i])
print(size)


(n, k) = [int(x) for x in input().strip().split(' ')]
a = [int(x) for x in input().strip().split(' ')]
s = [0] * k
for i in range(n):
	t = a[i] % k
	s[t] = s[t] + 1
ss = 0
for i in range(1, k + 1 >> 1):
	ss += max(s[i], s[k - i])
if k % 2 == 0:
	ss += min(1, s[k >> 1])
ss += min(1, s[0])
print(ss)


(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
modded = [0] * k
for i in a:
	modded[i % k] += 1
result = 0
for i in range(1, k // 2 + k % 2):
	if modded[i] > modded[k - i]:
		result += modded[i]
	else:
		result += modded[k - i]
if k % 2 == 0 and modded[k // 2] > 0:
	result += 1
if modded[0] > 0:
	result += 1
print(result)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
r = [set((j for j in a if j % k == i)) for i in range(k)]
print(bool(r[0]) + (0 if k & 1 else bool(r[k >> 1])) + sum((max(len(r[i]), len(r[k - i])) for i in range(1, k + 1 >> 1))))


(N, K) = map(int, input().split())
S = [int(x) for x in input().split()]
count = [0] * K
for x in S:
	count[x % K] += 1
size = 1 if count[0] else 0
if K & 1 == 0 and count[K >> 1]:
	size += 1
for i in range(1, K + 1 >> 1):
	size += max(count[i], count[K - i])
print(size)


import sys
(n, k) = map(int, input().split())
s = tuple(map(int, input().split()))

def solve(s, k):
	a = sorted([v % k for v in s])
	print(a, file=sys.stderr)
	cache = [0] * k
	for v in a:
		cache[v] += 1
	print(cache, file=sys.stderr)
	cnt = 0
	if cache[0] > 0:
		cnt += 1
	for i in range(1, k // 2 + 1):
		(a, b) = (cache[i], cache[k - i])
		if k == i * 2:
			if cache[i] > 0:
				cnt += 1
		else:
			cnt += max(a, b)
	return cnt
print(solve(s, k))


def read_ints():
	return [int(x) for x in input().strip().split(' ')]

def read_int():
	v = read_ints()
	return v[0]
(N, K) = read_ints()
ar = read_ints()
car = {v: 0 for v in range(K)}
for v in ar:
	car[v % K] += 1
maxsize = 0
if car[0] >= 1:
	maxsize += 1
del car[0]
if K % 2 == 0:
	if car[K // 2] >= 1:
		maxsize += 1
	del car[K // 2]
for k in range(1, (K - 1) // 2 + 1):
	ms = car[k]
	if car[K - k] > ms:
		ms = car[K - k]
	del car[k]
	del car[K - k]
	maxsize += ms
if K > 1:
	print(maxsize)
else:
	print(1)


import sys
from collections import Counter
(N, K) = [int(A_temp) for A_temp in input().strip().split(' ')]
ca = Counter([int(A_temp) % K for A_temp in input().strip().split(' ')])
r = int(ca[0] != 0) + int((K & 1 == 0) * (ca[K // 2] != 0))
for n in range(1, (K + 1) // 2):
	r += max(ca[n], ca[K - n])
print(r)


def make_remainder_dict(S):
	mod_dict = {}
	for num in S:
		remainder = num % k
		mod_dict[remainder] = mod_dict.get(remainder, [])
		mod_dict[remainder] += [num]
	return mod_dict
(n, k) = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]
mod_dict = make_remainder_dict(S)
sub_set_dict = {}
for (mod, vals) in mod_dict.items():
	if mod == 0 or mod == k / 2:
		sub_set_dict[mod] = [mod_dict[mod][0]]
	else:
		mod_b = k - mod
		vals_a = mod_dict[mod]
		vals_b = mod_dict.get(mod_b, [])
		if len(vals_a) >= len(vals_b):
			sub_set_dict[mod] = vals_a
		else:
			sub_set_dict[mod_b] = vals_b
print(sum([len(vals) for vals in sub_set_dict.values()]))


(_, k) = [int(x) for x in input().split()]
counts = [0] * k
for n in (int(x) for x in input().split()):
	counts[n % k] += 1
result = 0
for i in range(len(counts)):
	if 2 * i % k == 0:
		if counts[i]:
			result += 1
	elif counts[i] > counts[k - i]:
		result += counts[i]
print(result)


k = int(input().split()[1])
lst = list((int(i) for i in input().split()))
x = [0 for i in range(k)]
for i in lst:
	x[i % k] += 1
s = min(x.pop(0), 1)
while x:
	if len(x) == 1:
		s += min(1, x.pop())
	else:
		s += max(x.pop(0), x.pop())
print(s)


A = [int(A_temp) for A_temp in input().strip().split(' ')]
n = A[0]
k = A[1]
B = [int(A_temp) for A_temp in input().strip().split(' ')]

def sizele(A, t):
	i = 0
	for m in A:
		if m == t:
			i += 1
	return i

def size(A, t, k):
	i = 0
	j = 0
	if t == 0:
		return 1
	if k == 2 * t:
		return 1
	for m in A:
		if m == t:
			i += 1
		if m == k - t:
			j += 1
	return max(i, j)
for i in range(len(B)):
	B[i] = B[i] % k
A = []
for i2 in range(k):
	if i2 in B:
		A.append(i2)
C = []
for i in range(1, int(k / 2) + 1):
	if k - i in A:
		if i in A:
			C.append(i)
Cle = []
for i in A:
	if i not in C:
		if k - i not in C:
			Cle.append(i)
D = []
for i in C:
	D.append(size(B, i, k))
for j in Cle:
	if j == 0:
		D.append(1)
	else:
		D.append(sizele(B, j))
n = sum(D)
print(n)


import sys
import math
(N, K) = [int(x) for x in input().strip().split(' ')]
A = [int(x) for x in input().strip().split(' ')]
sizes = [0 for x in range(K)]
for i in range(len(A)):
	sizes[A[i] % K] += 1
result = 0
result = result + 1 if sizes[0] > 0 else result
result = result + 1 if K % 2 == 0 and sizes[K // 2] > 0 else result
for i in range(1, math.ceil(K / 2)):
	result += max(sizes[i], sizes[K - i])
print(result)


from bisect import *

def find(a, k):
	i = bisect_left(a, k)
	if i != len(a) and a[i] == k:
		return a[i]
	return -1

def count(a, k):
	i = bisect_left(a, k)
	j = bisect_right(a, k)
	return a[i:j].count(k)
(N, k) = map(int, input().strip().split())
nums = map(int, input().strip().split())
nums_mod_k = list(map(lambda x: x % k, nums))
nmk_sorted = sorted(nums_mod_k)
total = 0
if k % 2 == 0:
	for i in range(1, k // 2):
		total += max(count(nmk_sorted, i), count(nmk_sorted, k - i))
	even_k_over_2 = count(nmk_sorted, k // 2)
	if even_k_over_2 > 0:
		total += 1
else:
	for i in range(1, k // 2 + 1):
		total += max(count(nmk_sorted, i), count(nmk_sorted, k - i))
even_divisible_count = count(nmk_sorted, 0)
if even_divisible_count > 0:
	total += 1
print(total)


(n, k) = map(int, input().strip().split())
t = [int(i) for i in input().strip().split()]
db = [0 for i in range(0, k + 1)]
for i in t:
	db[i % k] += 1
sum = 0
if db[0] > 0:
	sum += 1
if k % 2 == 0 and db[int(k / 2)] > 0:
	db[int(k / 2)] = 1
for i in range(1, int(k / 2) + 1):
	sum += max(db[i], db[k - i])
	db[i] = 0
	db[k - i] = 0
print(sum)


import collections
total = 0
C = collections.Counter()
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
a = [int(a_temp) for a_temp in input().strip().split(' ')]
if k == 1:
	print(1)
else:
	P = 0
	for i in a:
		if i != 0:
			C[i % k] += 1
		else:
			P += 1
	if 0 in C:
		T = 1
		C.pop(0)
	else:
		T = 0
	hold = set()
	for i in C:
		if i not in hold:
			hold.add(i)
			b = k - i
			if b in C:
				if b == i:
					total += 1
				else:
					hold.add(b)
					r = max(C[i], C[b])
					total += r
			elif b not in C:
				total += C[i]
	if P > T:
		T = P
	print(total + T)


from collections import Counter
(n, k) = map(int, input().split())
S = [int(x) for x in input().split()]
remainders = Counter((x % k for x in S))
discarded = set()
size = 0
for (rem, count) in remainders.most_common():
	if 2 * rem in [0, k]:
		size += 1
		continue
	rem = min(rem, k - rem)
	if rem not in discarded:
		discarded.add(rem)
		size += count
print(size)


from collections import defaultdict
(_, k) = map(int, input().strip().split())
numbers = list(map(int, input().strip().split()))
hist = defaultdict(int)
for number in numbers:
	hist[number % k] += 1
members = 0
members += hist[0] > 0
for i in range(1, (k + 1) // 2):
	members += max(hist[i], hist[k - i])
if k % 2 == 0:
	members += hist[k // 2] > 0
print(members)


(n, k) = map(int, input().strip().split(' '))
arr = list(map(int, input().strip().split(' ')))
d = {x: [] for x in range(k)}
for i in range(n):
	d[arr[i] % k].append(arr[i])
count = 0
if len(d[0]) > 0:
	count = 1
S = set([(x, k - x) for x in range(1, k // 2 + 1)])
for (i, j) in S:
	if i != j:
		if len(d[i]) > len(d[j]):
			count += len(d[i])
		else:
			count += len(d[j])
	elif len(d[i]) > 0:
		count += 1
print(count)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
r = [0] * k
for i in range(n):
	r[a[i] % k] += 1
res = 0
for i in range(1, 1 + (k - 1) // 2):
	res += max(r[i], r[k - i])
if r[0] > 0:
	res += 1
if k % 2 == 0 and r[k // 2] > 0:
	res += 1
print(res)


(n, k) = map(int, input().split())
A = [int(x) % k for x in input().split()]
residues = {}
for i in range(k):
	residues[i] = 0
for a in A:
	residues[a] += 1
s = 0
for i in range(1, k // 2 + 1):
	s += max(residues[i], residues[k - i])
if k % 2 == 0 and residues[k // 2]:
	s -= residues[k // 2] - 1
if residues[0]:
	s += 1
print(s)


s = 0
(n, k) = input().strip().split(' ')
(n, k) = (int(n), int(k))
arr = sorted([int(arr_temp) % k for arr_temp in input().strip().split(' ')])
if arr.count(0) > 0:
	s = 1
for i in range(0, k // 2):
	s = s + max(arr.count(i + 1), arr.count(k - i - 1))
if k % 2 == 0:
	s = s - arr.count(k // 2) + 1
if s == 0:
	s = 1
print(s)


(n, k) = map(int, input().strip().split())
a = [int(s) for s in input().strip().split()]
mods = {}
for j in range(k):
	mods[j] = 0
subset = 0
for i in range(n):
	m = a[i] % k
	mods[m] += 1
if mods[0] > 0:
	subset += 1
if k % 2 == 0 and mods[k // 2] > 0:
	subset += 1
j = 1
while j < k / 2:
	subset += max(mods[j], mods[k - j])
	j += 1
print(max(1, subset))


from collections import Counter
(n, k) = map(int, input().split())
cnt = Counter([x % k for x in map(int, input().split())])
count = 2 if cnt[0] > 0 else 0
for i in range(1, k):
	if i == k - i:
		count += 2 if cnt[i] > 0 else 0
	else:
		count += max(cnt[i], cnt[k - i])
print(count // 2)


(n, k) = list(map(int, input().split()))
ar = list(map(int, input().split()))
a = {_: 0 for _ in range(k)}
for i in ar:
	a[i % k] += 1
count = 0
aa = range(1, k // 2)
count += min(1, a[0])
if k % 2 == 0:
	count += min(1, a[k // 2])
if k > 3:
	if k % 2 == 0:
		for j in range(1, k // 2):
			count += max(a[j], a[k - j])
	else:
		for j in range(1, k // 2 + 1):
			count += max(a[j], a[k - j])
elif k == 3:
	count += max(a[1], a[2])
print(count)


def max_nondiv_subset(arr, k):
	rem_cnt = {}
	for val in arr:
		r = val % k
		rem_cnt[r] = rem_cnt.get(r, 0) + 1
	ans = 0
	for i in range(1, (k - 1) // 2 + 1):
		ans += max(rem_cnt.get(i, 0), rem_cnt.get(k - i, 0))
	if k % 2 == 0:
		ans += min(rem_cnt.get(k // 2, 0), 1)
	ans += min(rem_cnt.get(0, 0), 1)
	return ans

def input_ints():
	return [int(x) for x in input().strip().split(' ')]
(_, k) = input_ints()
arr = input_ints()
print(max_nondiv_subset(arr, k))


(n, k) = map(int, input().split())
arr = map(int, input().split())
d = {i: 0 for i in range(k)}
for i in arr:
	d[i % k] += 1
s = 0
if d[0]:
	s += 1
if k % 2 == 0 and d[k / 2]:
	s += 1
for i in range(1, (k + 1) // 2):
	s += max(d[i], d[k - i])
print(s)


(n, k) = map(int, input().strip().split(' '))
arr = map(int, input().strip().split(' '))
rem_counts = [0] * k
for n in arr:
	rem_counts[n % k] += 1
total = 0
for i in range(1, (k - 1) // 2 + 1):
	total += max(rem_counts[i], rem_counts[k - i])
total += min(1, rem_counts[0])
if k % 2 == 0:
	total += min(1, rem_counts[k // 2])
print(total)


(n, k) = [int(i) for i in input().strip().split(' ')]
arr = [int(i) for i in input().strip().split(' ')]
arr = [i % k for i in arr]
cnt = k * [0]
for a in arr:
	cnt[a] += 1
max_size = 0
for i in range(k):
	if i == (k - i) % k:
		if cnt[i] > 0:
			max_size += 1
	elif cnt[i] > cnt[k - i]:
		max_size += cnt[i]
	elif cnt[i] == cnt[k - i] and i < k - i:
		max_size += cnt[i]
print(max_size)


(n, k) = input().strip().split()
(n, k) = (int(n), int(k))
A = [int(temp) for temp in input().strip().split()]
B = [x % k for x in A]
D = list(set(B))
for i in range(len(D)):
	if i >= len(D):
		break
	for j in range(len(B)):
		if k / 2 == D[i]:
			n -= B.count(D[i]) - 1
			if D[i] in B:
				B.remove(D[i])
			break
		elif D[i] + B[j] == k:
			if B.count(D[i]) > B.count(B[j]):
				n -= B.count(B[j])
				if B[j] in D:
					D.remove(B[j])
				break
			else:
				n -= B.count(D[i])
				if B[j] in D:
					D.remove(B[j])
				break
		elif D[i] == 0:
			n -= B.count(0) - 1
			break
print(n)


(N, K) = map(int, input().strip().split(' '))
A = list(map(int, input().strip().split(' ')))
R = [a % K for a in A]
ans = 0
for i in range(1, K // 2 + 1):
	j = K - i
	if i == j:
		if i in R:
			ans += 1
	else:
		ans += max(R.count(i), R.count(j))
if 0 in R:
	ans += 1
print(ans)


import collections

def len_maximal_subset(a, k):
	new = [x % k for x in a]
	c = collections.Counter(new)
	if k % 2 == 0:
		if k // 2 in c:
			c[k // 2] = 1
	total = int(0 in c)
	for i in range(1, k // 2 + 1):
		total += max(c[i], c[k - i])
	return total
(n, k) = map(int, input().strip().split())
a = set(map(int, input().strip().split()))
print(len_maximal_subset(a, k))


(n, k) = map(int, input().strip().split())
count = [0] * k
for i in map(lambda x: int(x) % k, input().strip().split()):
	count[i] += 1
print(min(1, count[0]) + (0 if k % 2 else min(1, count[k // 2])) + sum((max(count[i], count[k - i]) for i in range(1, (k + 1) // 2))))


n = list(map(int, input().split()))
arr = list(map(int, input().split()))
k = n[1]
d = {x: 0 for x in range(k)}
for x in arr:
	d[x % k] += 1
if d[0] != 0:
	sum = 1
else:
	sum = 0
i = 1
while i <= k // 2:
	if i != k - i:
		max = d[i]
		if d[k - i] > max:
			max = d[k - i]
		sum += max
	else:
		sum += 1
	i += 1
print(sum)


from collections import Counter
from math import ceil

def row(fn):
	return list(map(fn, input().strip().split()))
(n, k) = row(int)
A = row(int)
counter = Counter((a % k for a in A))
res = sum((max(counter[i], counter[k - i]) for i in range(1, int(ceil(k / 2)))))
res += min(1, counter[0]) + (0 if k % 2 else min(1, counter[k / 2]))
print(res)


(n, k) = [int(inp) for inp in input().strip().split(' ')]
A = [int(inp) for inp in input().strip().split(' ')]
D = dict(((k, 0) for k in range(k)))
for a in A:
	D[a % k] += 1
answer = 0
for i in range(1, (k + 1) // 2):
	answer += max(D[i], D[k - i])
if D[0] > 0:
	answer += 1
if k % 2 == 0 and D[k // 2] > 0:
	answer += 1
print(answer)


from collections import defaultdict
import math
from sys import stdin

def solve(s, k):
	if k == 1:
		return 1
	div_count = defaultdict(int)
	for n in s:
		div_count[n % k] += 1
	max_size = 0
	for i in range(1, math.ceil(k / 2)):
		max_size += max(div_count[i], div_count[k - i])
	if k % 2 == 0 and div_count[int(k / 2)] >= 1:
		max_size += 1
	if div_count[0] >= 1:
		max_size += 1
	return max_size
line1 = stdin.readline().split()
n = int(line1[0])
k = int(line1[1])
s = list(map(int, stdin.readline().split()))
print(solve(s, k))


import math
(dummy, bucket_num) = [int(e) for e in input().strip().split()]
nums = [int(e) for e in input().strip().split()]
if bucket_num == 1:
	print(1)
else:
	buckets = {}
	for n in range(bucket_num):
		buckets[n] = 0
	for n in nums:
		buckets[n % bucket_num] += 1
	answer = 1 if buckets[0] > 0 else 0
	for bucket in range(1, math.ceil(bucket_num // 2) + 1):
		if buckets[bucket] > buckets[bucket_num - bucket]:
			answer += buckets[bucket]
		else:
			answer += buckets[bucket_num - bucket]
	if bucket_num // 2 == bucket_num / 2:
		answer -= buckets[bucket_num / 2]
		if buckets[bucket_num / 2] > 0:
			answer += 1
	print(answer)


import math
[n, k] = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
ks = [0] * k
for a in arr:
	ks[a % k] += 1
for k0 in range(1, math.ceil(k / 2)):
	if ks[k0] > ks[k - k0]:
		ks[k - k0] = 0
	else:
		ks[k0] = 0
if ks[0] > 1:
	ks[0] = 1
if k % 2 == 0:
	if ks[k // 2] > 1:
		ks[k // 2] = 1
print(sum(ks))


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
remainder_count = [0] * k
for a_i in a:
	temp = a_i % k
	remainder_count[temp] += 1
answer = min(remainder_count[0], 1)
if k % 2 == 0:
	answer += min(remainder_count[int(k / 2)], 1)
i = 1
while i < k / 2:
	answer += max(remainder_count[i], remainder_count[k - i])
	i += 1
print(answer)


(n, k) = map(int, input().strip().split(' '))
a = [int(n) for n in input().strip().split(' ')]
count = 0
b = [i % k for i in a]
b.sort()
if 0 in b:
	count += 1
if k / 2 in b:
	count += 1
for i in range(1, (k + 1) // 2):
	if b.count(i) > b.count(k - i):
		count += b.count(i)
	else:
		count += b.count(k - i)
print(count)


from math import ceil
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
di = dict()
for i in range(k):
	di[i] = 0
for i in arr:
	di[i % k] += 1
ans = 0
for i in range(1, ceil(k / 2)):
	ans += max(di[i], di[k - i])
if k % 2 == 0 and di[k / 2] != 0:
	ans += 1
if di[0] != 0:
	ans += 1
print(ans)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
nums = [int(a_temp) for a_temp in input().strip().split(' ')]
max_pairs = 0
counts = {x: 0 for x in range(k)}
f = lambda x: x % k
remainders = list(map(f, nums))
for x in remainders:
	counts[x] += 1
if counts[0] >= 1:
	max_pairs += 1
pairs = []
for i in range(1, k // 2 + 1):
	pairs.append([i, k - i])
for (i, j) in pairs:
	if i == j:
		max_pairs += 1
	elif counts[i] > counts[j]:
		max_pairs += counts[i]
	else:
		max_pairs += counts[j]
print(max_pairs)


(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
d = {x: [] for x in range(k)}
for i in range(n):
	d[arr[i] % k].append(arr[i])
count = 0
if len(d[0]) > 0:
	count = 1
S = set([(x, k - x) for x in range(1, k // 2 + 1)])
for (i, j) in S:
	if i != j:
		if len(d[i]) > len(d[j]):
			count += len(d[i])
		else:
			count += len(d[j])
	elif len(d[i]) > 0:
		count += 1
print(count)


(n, k) = [int(x) for x in input().split()]
l = [int(x) % k for x in input().split()]
d = {}
c = 0
for i in l:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
if 0 in d:
	c += 1
d.pop(0, 0)
while d != {}:
	for i in d:
		if k - i == i:
			d.pop(k - i, 0)
			d.pop(i, 0)
			c += 1
		elif k - i in d:
			if d[k - i] > d[i]:
				c += d[k - i]
			else:
				c += d[i]
			d.pop(k - i, 0)
			d.pop(i, 0)
		else:
			c += d[i]
			d.pop(i, 0)
		break
print(c)


import sys
import random

def sample(n, k):
	import random
	l = list(range(n))
	for i in range(n):
		l[i] = random.sample(range(0, k), 1)[0]
	return l
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
a = [int(a_temp) for a_temp in input().strip().split(' ')]
m = [x % k for x in a]
count = 0
h = list(range(0, k))
for x in range(0, k):
	h[x] = sum([y == x for y in m])
S = set([(x, k - x) for x in range(1, k // 2 + 1)])
if h[0] > 0:
	count += 1
for (i, j) in S:
	if i != j:
		if h[i] <= h[j]:
			count += h[j]
		else:
			count += h[i]
	elif h[i] > 0:
		count += 1
print(count)


firstLine = input().split(' ')
n = int(firstLine[0])
k = int(firstLine[1])
secondLine = input().split(' ')
frequencies = dict()
for i in range(n):
	mod = int(secondLine[i]) % k
	if frequencies.get(mod):
		frequencies[mod] += 1
	else:
		frequencies[mod] = 1
count = n
if frequencies.get(0):
	count = count - frequencies.get(0) + 1
if k % 2 == 0:
	if frequencies.get(k / 2):
		count = count - frequencies.get(k / 2) + 1
	j = 1
	while j < k / 2:
		m = k - j
		if frequencies.get(m) and frequencies.get(j):
			count = count - min(frequencies.get(m), frequencies.get(j))
		j += 1
else:
	j = 1
	while j <= k / 2:
		m = k - j
		if frequencies.get(m) and frequencies.get(j):
			count = count - min(frequencies.get(m), frequencies.get(j))
		j += 1
print(count)


(n, k) = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))
mods = [len([x for x in arr if x % k == i]) for i in range(k)]
s = 0
i = 1
while i < k / 2:
	s += max(mods[i], mods[k - i])
	i += 1
if mods[0] > 0:
	s += 1
if mods[k // 2] > 0 and k % 2 == 0:
	s += 1
print(s)


if 1 == 2:
	f = open('in.txt')
	fkt = f.readline
else:
	fkt = input
from collections import Counter
import sys, math
(n, k) = map(int, fkt().strip().split(' '))
S = list(map(lambda x: int(x) % k, fkt().strip().split(' ')))
S = Counter(S)
c = 0
for s in range(1, math.ceil(k / 2)):
	if not s in S and k - s in S:
		c += S[k - s]
	elif s in S and (not k - s in S):
		c += S[s]
	elif s in S and k - s in S:
		c += max(S[s], S[k - s])
if 0 in S:
	c += 1
if k % 2 == 0 and k // 2 in S:
	c += 1
print(c)


import sys
(n, k) = map(int, input().strip().split(' '))
arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
d = {x: [] for x in range(k)}
for i in range(n):
	d[arr[i] % k].append(arr[i])
count = 0
if len(d[0]) > 0:
	count = 1
S = set([(x, k - x) for x in range(1, k // 2 + 1)])
for (i, j) in S:
	if i != j:
		if len(d[i]) > len(d[j]):
			count += len(d[i])
		else:
			count += len(d[j])
	elif len(d[i]) > 0:
		count += 1
print(count)


(n, k) = input().split()
(n, k) = (int(n), int(k))
a = [int(x) for x in input().split()]
buck = [0] * k
for i in a:
	buck[i % k] += 1
res = int(buck[0] > 0)
if k % 2 == 0:
	to = k // 2
	res += int(buck[to] > 0)
else:
	to = k // 2 + 1
for i in range(1, to):
	res += max(buck[i], buck[k - i])
print(res)


(n, k) = input().strip().split()
(n, k) = (int(n), int(k))
temp = input().strip().split()
dict_remainders = {}
for i in range(k):
	dict_remainders[i] = 0
for num in temp:
	num = int(num)
	dict_remainders[num % k] += 1
if dict_remainders[0] > 0:
	max_size = 1
else:
	max_size = 0
i = 1
while i <= k - i:
	if i == k - i:
		max_size += 1
	elif dict_remainders[i] > dict_remainders[k - i]:
		max_size += dict_remainders[i]
	else:
		max_size += dict_remainders[k - i]
	i += 1
print(max_size)


(n, k) = (int(x) for x in input().strip().split(' '))
counts = [0] * k
total = 0
for x in input().strip().split(' '):
	counts[int(x) % k] += 1
for i in range(1, (k + 1) // 2):
	total += max(counts[i], counts[-i])
if k & 1 == 0 and counts[k // 2] > 0:
	total += 1
if counts[0] > 0:
	total += 1
print(total)


import operator
import sys
(n, k) = [int(x) for x in input().strip().split(' ')]
arr = [int(arr_temp) % k for arr_temp in input().strip().split(' ')]
counts = {x: sum((1 for i in arr if i == x)) for x in range(k)}
length = 0
for x in range(1, int(k / 2 + k % 2)):
	inv = k - x
	length += max(counts[x], counts[inv])
if k % 2 == 0 and counts[k / 2] > 0:
	length += 1
if counts[0] >= 1:
	length += 1
print(length)


(n, k) = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))
d = {x: [] for x in range(k)}
for i in range(n):
	d[arr[i] % k].append(arr[i])
count = 0
if len(d[0]) > 0:
	count = 1
S = set([(x, k - x) for x in range(1, k // 2 + 1)])
for (i, j) in S:
	if i != j:
		if len(d[i]) > len(d[j]):
			count += len(d[i])
		else:
			count += len(d[j])
	elif len(d[i]) > 0:
		count += 1
print(count)


def process_arr(arr, k):
	arr_dict = {}
	for i in range(0, k):
		arr_dict[i] = 0
	for i in range(0, len(arr)):
		v = arr[i] % k
		arr_dict[v] = arr_dict[v] + 1
	return arr_dict

def devide_arr(arr_dict, k):
	max_count = 0
	for i in range(0, int(k / 2) + 1):
		if i == k / 2 and k % 2 == 0 or i == 0:
			if arr_dict[i] > 0:
				max_count = max_count + 1
		else:
			max_count = max_count + max(arr_dict[i], arr_dict[k - i])
	return max_count
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
arr = input().strip().split(' ')
arr = [int(i) for i in arr]
if k == 1:
	print(1)
else:
	arr_dict = process_arr(arr, k)
	print(devide_arr(arr_dict, k))


import math
from collections import Counter
(n, k) = [int(e) for e in input().strip().split(' ')]
arr = [int(e) for e in input().strip().split(' ')]
arr = [e % k for e in arr]
carr = Counter(arr)
number = 0
number += min(carr[0], 1)
if k % 2 == 0:
	number += min(carr[k // 2], 1)
for i in range(1, math.ceil(k / 2)):
	number += max(carr[i], carr[k - i])
print(number)


(n, k) = input().split()
(n, k) = (int(n), int(k))
a = [int(x) for x in input().split()]
r = [0] * k
for i in range(n):
	r[a[i] % k] += 1
res = 0
for i in range(1, k // 2 + 1):
	if i == k - i and r[i] > 0:
		res += 1
	else:
		res += max(r[i], r[k - i])
if r[0] > 0:
	res += 1
print(res)


(n, k) = input().strip().split(' ')
(n, k) = (int(n), int(k))
a = input().strip().split(' ')
a = [int(i) for i in a]
groups = [0] * k
for i in range(n):
	r = a[i] % k
	groups[r] += 1
for i in range(k):
	if 2 * i % k == 0:
		groups[i] = min(groups[i], 1)
total = groups[0]
for i in range(1, (k + 2) // 2):
	total += max(groups[i], groups[k - i])
print(total)


from collections import Counter
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
cnt = Counter([x % k for x in A])
count = 0
if cnt[0] > 0:
	count = 1
S = set([(x, k - x) for x in range(1, k // 2 + 1)])
for (i, j) in S:
	if i != j:
		if cnt[i] > cnt[j]:
			count += cnt[i]
		else:
			count += cnt[j]
	elif cnt[i] > 0:
		count += 1
print(count)


import sys
(n, k) = input().strip().split(' ')
k = int(k)
arr = [int(a) for a in input().strip().split(' ')]
dic = {}
for i in range(0, k):
	dic[i] = 0
for i in arr:
	dic[i % k] += 1
count = 0
if dic[0] > 0:
	count = 1
i = 1
j = k - 1
while i < j:
	count += max(dic[i], dic[j])
	i += 1
	j -= 1
if i == j and dic[i] > 0:
	count += 1
print(count)


(n, k) = input().strip().split(' ')
(n, k) = (int(n), int(k))
tmp = [0] * k
for a in input().strip().split(' '):
	tmp[int(a) % k] += 1
sum = 0
for i in range(1, (k + 1) // 2):
	sum += tmp[i] if tmp[i] > tmp[k - i] else tmp[k - i]
if k % 2 == 0 and tmp[k // 2] > 0:
	sum += 1
if tmp[0] > 0:
	sum += 1
print(sum)


(n, k) = input().split()
k = int(k)
arr = [int(x) for x in input().split()]
subset = [0] * k
for x in arr:
	p = x % k
	subset[p] = subset[p] + 1
totLen = 0
if k % 2 == 0:
	mid = k // 2 - 1
	if subset[mid + 1] > 0:
		totLen += 1
else:
	mid = k // 2
for i in range(1, mid + 1):
	if subset[i] > subset[k - i]:
		totLen += subset[i]
	else:
		totLen += subset[k - i]
if subset[0] > 0:
	totLen += 1
print(totLen)