G. Gift
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Little S has designed a problem and plans to give it as a gift to everyone.

You are given an integer sequence $$$a_1,a_2,\cdots,a_n$$$.

Output any non-empty subsequence $$$a_{b_1},a_{b_2},\cdots,a_{b_k}$$$ of this sequence that satisfies $$$$$$ \left(\sum_{i=1}^ka_{b_i}\right)\bmod n=0 $$$$$$ It can be shown that such a subsequence always exists.

After reading the problem, Little L explains some basic concepts to everyone:

For any integer $$$k$$$ satisfying $$$1\le k\le n$$$ and any integers $$$b_1,\dots,b_k$$$ satisfying $$$$$$ 1\le b_1 \lt b_2 \lt \cdots \lt b_k\le n $$$$$$ we say that $$$a_{b_1},a_{b_2},\cdots,a_{b_k}$$$ is a non-empty subsequence of $$$a_1,a_2,\cdots,a_n$$$.

Regarding the summation symbol $$$\sum$$$, its meaning is $$$$$$ \sum_{i=1}^ka_{b_i}=a_{b_1}+a_{b_2}+\cdots+a_{b_k} $$$$$$ Here, the operation $$$\bmod$$$ is defined as $$$$$$ x\bmod y=x-\left\lfloor\frac{x}{y}\right\rfloor y $$$$$$ where $$$\lfloor z\rfloor$$$ denotes the greatest integer less than or equal to $$$z$$$. The condition $$$x\bmod y=0$$$ is equivalent to saying that $$$x$$$ is a multiple of $$$y$$$.

Input

The first line contains a single integer $$$T$$$ ($$$T\ge1$$$), denoting the number of test cases.

Then for each test case:

  • The first line contains a single integer $$$n$$$ ($$$n\ge1$$$).
  • The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n$$$ ($$$1\le a_i\le10^9$$$).
It is guaranteed that the sum of $$$n$$$ over all $$$T$$$ test cases does not exceed $$$10^6$$$.
Output

For each test case, output two lines:

  • The first line should contain a single integer $$$k$$$.
  • The second line should contain $$$k$$$ integers $$$b_1,b_2,\cdots,b_k$$$.
You must ensure that:
  • $$$1\le k\le n$$$.
  • $$$1\le b_1 \lt b_2 \lt \cdots \lt b_k\le n$$$.
  • $$$(a_{b_1}+a_{b_2}+\cdots+a_{b_k})\bmod n=0$$$.
If there are multiple valid answers, you only need to output any one of them.
Example
Input
2
6
1 1 4 5 1 4
6
1 1 4 5 1 4
Output
2
2 4
5
1 2 3 4 5
Note

In the first test case, $$$a_2+a_4=1+5=6$$$ and $$$6\bmod6=0$$$, so the requirements are satisfied.

In the second test case, $$$a_1+a_2+a_3+a_4+a_5=1+1+4+5+1=12$$$ and $$$12\bmod6=0$$$, so the requirements are satisfied.