Counting Pairs

Input

The first line contains single integer $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — the number of test cases.

The first line contains single integer $n$ $(1 \leq n \leq 1 0^{6})$ (1 \le n \le 10^6) — the length of array $a$ .

The second line contains $n$ separated integers $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) — the array $a$ .

It's guaranteed that $\sum n \leq 1 0^{6}$ \sum n \le 10^6 overall test cases.

Output

For each test case , single integer — the count of required output answer modulus 1e6+3 pairs

Examples

Example 1

Loading

Scoring

Subtask $1$ ( $10$ points) : $(1 \leq \sum n \leq 1000)$ (1 \le \sum n \le 1000) and $(1 \leq a_{i} \leq 9)$ (1 \le a_i \le 9)
Subtask $2$ ( $40$ points) : $(1 \leq a_{i} \leq 4)$ (1 \le a_i \le 4)
Subtask $3$ ( $50$ points) : No additional constraints