Підрахунок пар

Вхідні дані

Перший рядок містить одне ціле число $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — кількість тестових випадків.

Другий рядок містить одне ціле число $n$ $(1 \leq n \leq 1 0^{6})$ (1 \le n \le 10^6) — довжина масиву $a$ .

Третій рядок містить $n$ розділених цілих чисел $a_{1}, a_{2}, .., a_{n}$ a_1,a_2,..,a_n $(1 \leq a_{1}, a_{2}, a_{3}, ..., a_{n} \leq 1 0^{9})$ (1 \le a_1,a_2,a_3,...,a_n \le 10^9) — масив $a$ .

Гарантується, що загальна кількість тестових випадків $\sum n \leq 1 0^{6}$ \sum n \le 10^6.

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число — необхідну вивід відповіді за модулем 1e6+3 кількість пар.

Приклади

Приклад 1

Loading

Оцінювання

Підзадача $1$ ( $10$ балів) : $(1 \leq \sum n \leq 1000)$ (1 \le \sum n \le 1000) та $(1 \leq a_{i} \leq 9)$ (1 \le a_i \le 9)
Підзадача $2$ ( $40$ балів) : $(1 \leq a_{i} \leq 4)$ (1 \le a_i \le 4)
Підзадача $3$ ( $50$ балів) : Додаткових обмежень немає