A. Cut the Array
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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$$$.

Example
Input
4
6
1 2 3 4 5 6
4
1 3 3 7
3
2 1 0
5
7 2 6 2 4
Output
3 5
0 0
1 2
2 4
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$$$.