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 = (\sum\limits_{i=1}^{l} a_i) \bmod 3$$$;
$$$s_2 = (\sum\limits_{i=l+1}^{r} a_i) \bmod 3$$$;
$$$s_3 = (\sum\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$$$.

Cut the Array

Examples