You are given an array of $n$ non-negative integers $[a_1, a_2, \dots, a_n]$.

Your task is to cut it into three non-empty parts: a prefix, a middle part, and a suffix. Formally, you need to choose two integers $l$ and $r$ such that $1 \le l \lt r \lt n$, and obtain three parts:

• the prefix up the element at index $l$ inclusive (i.e., $[a_1, a_2, \dots, a_l]$);
• the central part from the element at index $l+1$ to the element at index $r$ inclusive (i.e., $[a_{l+1}, a_{l+2}, \dots, a_r]$);
• the suffix from the element at index $r+1$ to $n$ inclusive (i.e., $[a_{r+1}, a_{r+2}, \dots, a_n]$).

Let $s_1, s_2, s_3$ be the remainders of the sums of these parts modulo $3$. In other words:

• s_1 = ( um\limits_{i=1}^{l} a_i) \bmod 3;
• s_2 = ( um\limits_{i=l+1}^{r} a_i) \bmod 3;
• s_3 = ( um\limits_{i=r+1}^{n} a_i) \bmod 3.

Your task is to find such boundaries $l$ and $r$ that either all numbers $s_1, s_2, s_3$ are different, or all numbers $s_1, s_2, s_3$ are the same.

Input

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Each test case consists of two lines:

• the first line contains a single integer $n$ ($3 \le n \le 40$);
• the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 40$).

Output

For each test case, if a suitable pair of integers $l$ and $r$ ($1 \le l \lt r \lt n$) exists, output these two integers (if there are multiple suitable pairs, you can output any of them). Otherwise, output two integers equal to $0$.

Note

Consider the examples from the statement:

• in the first example, the array is cut into parts $[1, 2, 3]$, $[4, 5]$, $[6]$; $s_1 = s_2 = s_3 = 0$;
• in the second example, there is no suitable cut;
• in the third example, the array is cut into parts $[2]$, $[1]$, $[0]$; $s_1 = 2$, $s_2 = 1$, $s_3 = 0$;
• in the fourth example, the array is cut into parts $[7, 2]$, $[6, 2]$, $[4]$; $s_1 = 0$, $s_2 = 2$, $s_3 = 1$.

Samples

4
6
1 2 3 4 5 6
4
1 3 3 7
3
2 1 0
5
7 2 6 2 4

3 5
0 0
1 2
2 4