No testdata at current.

No submission language available for this problem.

Background

You are given an array of integers a1,a2,…,an. You can perform the following operation any number of times (possibly zero):

• Choose any element ai from the array and change its value to any integer between 0 and ai (inclusive). More formally, if ai<0, replace ai with any integer in [ai,0], otherwise replace ai with any integer in [0, ai].

Description

Let $r$ be the minimum possible product of all the $a_i$ after performing the operation any number of times.

Find the minimum number of operations required to make the product equal to $r$. Also, print one such shortest sequence of operations. If there are multiple answers, you can print any of them.

Format

Input

Each test consists of multiple test cases. The first line contains a single integer t (1≤t≤500) - the number of test cases. This is followed by their description.

The first line of each test case contains the a single integer n (1≤n≤100) — the length of the array.

The second line of each test case contains n integers a1,a2,…,an ($−10^9≤a_i≤10^9$).

Output

For each test case:

The first line must contain the minimum number of operations $k(0≤k≤n)$.

The $j$-th of the next $k$lines must contain two integers $i$ and $x$, which represent the $j$-th operation. That operation consists in replacing $a_i$ with $x$.

Samples

4
1
155
4
2 8 -1 3
4
-1 0 -2 -5
4
-15 -75 -25 -30

1
1 0
0
0
1
3 0

Limitation

1s, 1024KiB for each test case.

#include <iostream>
#include <cstring>
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	int *a = new int [n + 10];
	
	int ocnt, icnt, cnt0;
	ocnt = icnt = cnt0 = 0;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		if (a[i] > 0) ocnt ++;
		if (a[i] < 0) icnt ++;
		if (a[i] == 0) cnt0 ++; 
	}
	
	if (cnt0 > 0) {
		cout << 0 << endl;
	} else if (icnt % 2 == 0) {
		cout << 1 << endl << 1 << " " << 0 << endl; 
	} else {
		cout << 0 << endl;
	}
	
	delete []a; 
}
 
int main() {
	
	int t;
	cin >> t;
	for (int i = 1; i <= t; i ++) {
		solve();
	} 
	
	return 0;
}