Задається масив \(A\) розміру \(N\) та ціле число \(M\).

Потрібно знайти максимальне значення суми підмасиву за модулем \(M\).

По модулю слід розуміти як залишок від ділення: наприклад, 37 mod 25 дорівнює 12; 7 mod 5 дорівнює 2.

Підмасив це неперервна підмножина елементів масиву.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(T\) - кількість тестів.

Перший рядок тесту містить цілі числа \(N, M\).

Наступний рядок тесту містить \(N\) цілих чисел \(A_i\).

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести відповідь.

Обмеження

\(1 \le T \le 10\)

\(2 \le N \le 10^3\)

\(1 \le M \le 10^{5}\)

\(1 \le A_i \le 10^{3}\)

\(\sum N \le 5000\)

Пояснення до прикладу

Максимально можлива сума по модулю 7 рівна 6. ЇЇ можна отримати просумувавши два перші елементи масиву.

Приклад вхідних даних

1
5 7
3 3 9 9 5

Приклад вихідних даних

6