310677: CF1869A. Make It Zero

A. Make It Zerotime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

During Zhongkao examination, Reycloer met an interesting problem, but he cannot come up with a solution immediately. Time is running out! Please help him.

Initially, you are given an array $a$ consisting of $n \ge 2$ integers, and you want to change all elements in it to $0$.

In one operation, you select two indices $l$ and $r$ ($1\le l\le r\le n$) and do the following:

• Let $s=a_l\oplus a_{l+1}\oplus \ldots \oplus a_r$, where $\oplus$ denotes the bitwise XOR operation;
• Then, for all $l\le i\le r$, replace $a_i$ with $s$.

You can use the operation above in any order at most $8$ times in total.

Find a sequence of operations, such that after performing the operations in order, all elements in $a$ are equal to $0$. It can be proven that the solution always exists.

Input

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

The first line of each test case contains a single integer $n$ ($2\le n\le 100$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0\le a_i\le 100$) — the elements of the array $a$.

Output

For each test case, in the first line output a single integer $k$ ($0\le k\le 8$) — the number of operations you use.

Then print $k$ lines, in the $i$-th line output two integers $l_i$ and $r_i$ ($1\le l_i\le r_i\le n$) representing that you select $l_i$ and $r_i$ in the $i$-th operation.

Note that you do not have to minimize $k$. If there are multiple solutions, you may output any of them.

ExampleInput

6
4
1 2 3 0
8
3 1 4 1 5 9 2 6
6
1 5 4 1 4 7
5
0 0 0 0 0
7
1 1 9 9 0 1 8
3
100 100 0

Output

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

Note

In the first test case, since $1\oplus2\oplus3\oplus0=0$, after performing the operation on segment $[1,4]$, all the elements in the array are equal to $0$.

In the second test case, after the first operation, the array becomes equal to $[3,1,4,15,15,15,15,6]$, after the second operation, the array becomes equal to $[0,0,0,0,0,0,0,0]$.

In the third test case:

Operation	$a$ before		$a$ after
$1$	$[\underline{1,5},4,1,4,7]$	$\rightarrow$	$[4,4,4,1,4,7]$
$2$	$[4,4,\underline{4,1},4,7]$	$\rightarrow$	$[4,4,5,5,4,7]$
$3$	$[4,4,5,5,\underline{4,7}]$	$\rightarrow$	$[4,4,5,5,3,3]$
$4$	$[\underline{4,4,5},5,3,3]$	$\rightarrow$	$[5,5,5,5,3,3]$
$5$	$[5,5,5,\underline{5,3,3}]$	$\rightarrow$	$[5,5,5,5,5,5]$
$6$	$[\underline{5,5,5,5,5,5}]$	$\rightarrow$	$[0,0,0,0,0,0]$

In the fourth test case, the initial array contains only $0$, so we do not need to perform any operations with it.

题目大意：给定一个长度至少为2的整数数组a，通过不超过8次操作，使得数组中所有元素变为0。每次操作可以选择两个索引l和r，计算l到r之间所有元素的异或和s，然后将l到r之间的所有元素替换为s。要求输出操作次数k以及每次操作选择的两个索引l和r。

输入数据格式：第一行一个整数t，表示测试用例的数量。接下来每个测试用例有两行，第一行一个整数n，表示数组a的长度，第二行n个整数，表示数组a的元素。

输出数据格式：对于每个测试用例，第一行输出一个整数k，表示操作次数。接下来k行，每行输出两个整数l和r，表示每次操作选择的两个索引。题目大意：给定一个长度至少为2的整数数组a，通过不超过8次操作，使得数组中所有元素变为0。每次操作可以选择两个索引l和r，计算l到r之间所有元素的异或和s，然后将l到r之间的所有元素替换为s。要求输出操作次数k以及每次操作选择的两个索引l和r。 输入数据格式：第一行一个整数t，表示测试用例的数量。接下来每个测试用例有两行，第一行一个整数n，表示数组a的长度，第二行n个整数，表示数组a的元素。 输出数据格式：对于每个测试用例，第一行输出一个整数k，表示操作次数。接下来k行，每行输出两个整数l和r，表示每次操作选择的两个索引。