Longest Non-Divisible Subsequence

Given a list of N integers and an integer K, your task is to find the length of the longest subsequence such that for any two elements a and b in the subsequence, the sum a + b is not divisible by K. In other words, for every pair (a, b) in the subsequence, it must be that:

$$ (a+b) \mod K \neq 0 $$

This problem is a variation of the well-known "Non-Divisible Subset" problem. A common strategy is to count the frequency of each remainder when the array elements are divided by K and then carefully choose the maximum possible numbers from these groups without violating the condition.

Example:

Input: 6 4
       19 10 12 24 25 22
Output: 3

Here, the longest subsequence that satisfies the required condition has a length of 3.

inputFormat

The first line contains two integers N and K separated by a space.

The second line contains N space-separated integers representing the array elements.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ K ≤ 10³
• Each element of the array is a non-negative integer.

outputFormat

Output a single integer representing the length of the longest subsequence where the sum of any two elements is not divisible by K.

## sample

6 4
19 10 12 24 25 22

3

</p>