Largest Non-Divisible Subset

Given an array of integers and an integer \( k \), find the size of the largest subset such that the sum of any two distinct elements in this subset is not divisible by \( k \). In other words, for any two elements \( a \) and \( b \) in the subset (with \( a \neq b \)), it must hold that:

\( (a + b) \mod k \neq 0 \)

The problem can be solved by counting the remainder frequencies when each number is divided by \( k \) and handling complementary remainders accordingly.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

The first line contains two space-separated integers ( n ) and ( k ) where ( n ) is the size of the array and ( k ) is the divisor.

The second line contains ( n ) space-separated integers, representing the array elements.

outputFormat

Output a single integer which is the size of the largest subset satisfying the condition that the sum of any two numbers in the subset is not divisible by ( k ). The result should be printed to standard output (stdout).## sample

4 3
1 7 2 4

3