Problem: Nastia has received an array of n positive integers as a gift.

She calls such an array a good that for all i (2 ≤ i ≤ n) takes place gcd(a_{i - 1}, a_{i}) = 1, where gcd(u, v) denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers u and v.

You can perform the operation: select two different indices i, j (1 ≤ i, j ≤ n, i ≠ j) and two integers x, y (1 ≤ x, y ≤ 2 ⋅ 10^9) so that min{(a_i, a_j)} = min{(x, y)}. Then change a_i to x and a_j to y.

The girl asks you to make the array good using at most n operations.

It can be proven that this is always possible.

Input

The first line contains a single integer t (1 ≤ t ≤ 10 000) — the number of test cases.

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

The second line of each test case contains n integers a_1, a_2, …, a_{n} (1 ≤ a_i ≤ 10^9) — the array which Nastia has received as a gift.

It's guaranteed that the sum of n in one test doesn't exceed 2 ⋅ 10^5.

Output

For each of t test cases print a single integer k (0 ≤ k ≤ n) — the number of operations. You don't need to minimize this number.

In each of the next k lines print 4 integers i, j, x, y (1 ≤ i ≠ j ≤ n, 1 ≤ x, y ≤ 2 ⋅ 10^9) so that min{(a_i, a_j)} = min{(x, y)} — in this manner you replace a_i with x and a_j with y.

If there are multiple answers, print any.

Example

Input


2
5
9 6 3 11 15
3
7 5 13


Output


2
1 5 11 9
2 5 7 6
0

Note

Consider the first test case.

Initially a = [9, 6, 3, 11, 15].

In the first operation replace a_1 with 11 and a_5 with 9. It's valid, because min{(a_1, a_5)} = min{(11, 9)} = 9.

After this a = [11, 6, 3, 11, 9].

In the second operation replace a_2 with 7 and a_5 with 6. It's valid, because min{(a_2, a_5)} = min{(7, 6)} = 6.

After this a = [11, 7, 3, 11, 6] — a good array.

In the second test case, the initial array is already good.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.lang.Math;

public class Main{
	static BufferedReader reader;
	static StringTokenizer tokenizer;
	static PrintWriter writer;

	static int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	static long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	static double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	static String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}
	static String nexts() throws IOException {
	  	  tokenizer = new StringTokenizer(reader.readLine());
	   	 String s="";
	   	 while (tokenizer.hasMoreTokens()) {
			s+=tokenizer.nextElement()+" ";
		}
		return s;
	}
	public static int gcd(int x, int y){
		if (y == 0) return x; else return gcd(y, x % y);
	}

	public static boolean isPrime(int nn) 
	    { 
	         if(nn<=1){
		 return false; }
	        if(nn<=3){
		 return true; }
	      if (nn%2==0||nn%3==0){
		 return false; }
	        for (int i=5;i*i<=nn;i=i+6){ 
	            if(nn%i==0||nn%(i+2)==0){
	            	return false;  }
	            }
	         return true; 
	    } 

	public static void shuffle(int[] A) {
		for (int i = 0; i < A.length; i++) {
			int j = (int)(i * Math.random());
			int tmp = A[i];
			A[i] = A[j];
			A[j] = tmp;
		}
	}
	public static void shufflel(Long[] A) {
		for (int i = 0; i < A.length; i++) {
			int j = (int)(i * Math.random());
			long tmp = A[i];
			A[i] = A[j];
			A[j] = tmp;
		}
	}

	public static String reverse(String input)
 	   {
	        StringBuilder input2=new StringBuilder();
	        input2.append(input);
	        input2 = input2.reverse();
	        return input2.toString();
	    }


	 public static long power(int x, long n)
	{
	//    long mod = 1000000007;
		if (n == 0) {
			return 1;
		}

		long pow = power(x, n / 2);

		if ((n & 1) == 1) {
			return (x * pow * pow);
		}
		return (pow * pow);
	}
	public static long power(long x, long y, long p)     //x^y%p
	    { 
  	       long res = 1; 
	       x = x % p; 
  	       while (y > 0) { 
 	 	 if (y % 2 == 1) {
      	        	        res = (res * x) % p; 
		 }
  		 y = y >> 1; // y = y/2 
     	     	 x = (x * x) % p; 
     	         } 
  	         return res; 
    	} 

	 static long ncr(int n, int k)  
   	 { 
           		 long res = 1; 
  		   // Since C(n, k) = C(n, n-k)  
 		       if (k > n - k) { 
     		       k = n - k; 
      		  } 
  		  // Calculate value of [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]  
     		   for (int i = 0; i < k; ++i) { 
        		    res *= (n - i); 
         		   res /= (i + 1); 
     		   } 
  		  return res; 
 	   }
	public static int inv(int a, int m)     //Returns modulo inverse of a with respect to m using extended euclid algorithm
	    { 
	        int m0=m,t,q; 
	        int x0=0,x1=1; 
      	        if(m==1){
	                return 0; }
                 	         while(a>1) 
     	        {  
   	                q=a/m; 
    	                t=m; 
                                 m=a%m;a=t; 
    	                t=x0; 
     	                x0=x1-q*x0; 
      	                x1=t; } 
    	          if(x1<0){
 	   	 x1+=m0; }
   	           return x1; 
	    } 

	static int modInverse(int n, int p) 
  	{ 
    	          return (int)power((long)n, (long)(p - 2),(long)p); 
	 } 
	static int ncrmod(int n, int r, int p) 
   	 { 
	        if (r == 0)        // Base case 
	            return 1; 
  	        int[] fac = new int[n + 1];         // Fill factorial array so that we can find all factorial of r, n and n-r 
	        fac[0] = 1; 
	        for (int i = 1; i <= n; i++) 
                                     fac[i] = fac[i - 1] * i % p; 
   	         return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;     //IMPORTANT
    	}	 

	static int upper(int a[], int x)   //Returns rightest index of x in sorted arr else -1
  	  {                                                //If not present returns index of just smaller element
  	            int n=a.length;
    	        int l=0;
                int r=n-1;
                int ans=-1;
                while(l<=r){
                    int m=(r-l)/2+l;
                    if(a[m]<=x){
                        ans=m;
                        l=m+1;
                    }
                    else{
                        r=m-1;
                    }
                }
                 return ans;  
                } 
	static int lower(int a[], int x)     //Returns leftest index of x in sorted arr else n
 	   {                                                  //If not present returns index of just greater element
 	            int n=a.length;
   	            int l=0;
                int r=n-1;
                int ans=n;
                while(l<=r){
                    int m=(r-l)/2+l;
                    if(a[m]>=x){
                        ans=m;
                        r=m-1;
                    }
                    else{
                         l=m+1;
                    }
                }
                 return ans; 
                 } 

	public static long stringtoint(String s){ // Convert bit string to number
		long a = 1;
		long ans = 0;
		StringBuilder sb = new StringBuilder();
		sb.append(s);  
		sb.reverse();
		s=sb.toString();
		for(int i=0;i<s.length();i++){
			ans = ans + a*(s.charAt(i)-'0');
			a = a*2;
		}
		return ans;
	}
 
	String inttostring(long a,long m){        // a is number and m is length of string required
		String res = "";                     // Convert a number in bit string representation
		for(int i=0;i<(int)m;i++){
			if((a&(1<<i))==1){
				res+='1';
			}else
				res+='0';
		}
		StringBuilder sb = new StringBuilder();
		sb.append(res);  
		sb.reverse();
		res=sb.toString();
		return res;
    }
	
	 static class R implements Comparable<R>{
	        int x, y;
	        public  R(int x, int y) {           //a[i]=new R(x,y);
	            this.x = x;
	            this.y = y;
	        }
	        public int compareTo(R o) {
            		return x-o.x;     //Increasing order(Which is usually required)
        		}
	    }   
/*   FUNCTION TO SORT HASHMAP ACCORDING TO VALUE
//USE IT AS FOLLOW	

//Make a new list
List<Map.Entry<Integer, Integer> > list = 
               new LinkedList<Map.Entry<Integer, Integer> >(h.entrySet()); 
  
        // Sort the list 
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer> >() { 
            public int compare(Map.Entry<Integer, Integer> o1,  
                               Map.Entry<Integer, Integer> o2) 
            { 
                return (o1.getValue()).compareTo(o2.getValue());     //This is used to sort string stored as VALUE, use below function here accordingly
            } 
        }); 
          
        // put data from sorted list to new hashmap  
        HashMap<String, Integer> temp = new LinkedHashMap<String, Integer>(); 
        for (Map.Entry<String, Integer> aa : list) { 
            temp.put(aa.getKey(), aa.getValue()); 
        } 
        return temp;   //Now temp is our new sorted hashmap
OR
	for(int i = 0;i<h.size();i++)  //accessing elements from the list made
		{
			int count = list.get(i).getValue();    //Value
			while(count >= 0)
			{
					int key=list.get(i).getKey();  //key
					count -- ;
			}
		}

////////////////////////////////////////////////////////////////////////////////////////
public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) 
	{
		if(o1.getValue() != o2.getValue())
			return o1.getValue() > o2.getValue()?1:-1;  //Sorts Value in increasing order
		else if(o1.getValue() == o2.getValue()){
			return o1.getKey() > o2.getKey() ? 1:-1;  //If value equal, then sorts key in increasing order
		}
		
		return Integer.MIN_VALUE;
	}
*/
//Check if palindrome string - System.out.print(A.equals(new StringBuilder(A).reverse().toString())?"Yes":"No");
	public static void main(String[] args) throws IOException {
		reader = new BufferedReader(new InputStreamReader(System.in));
		tokenizer = null;
		writer = new PrintWriter(System.out);
		solve();
		reader.close();
		writer.close();
	}
	
	private static void solve() throws IOException {
		int t = nextInt();
		ArrayList<Integer> ar=new ArrayList<Integer>();
		while(t-->0){
			//String s= nextToken();
			//String[] s = str.split("\\s+");
		//	ArrayList<Integer> ar=new ArrayList<Integer>();
			//HashSet<Integer> set=new HashSet<Integer>();
			//HashMap<Integer,String> h=new HashMap<Integer,String>();
			//R[] a1=new R[n];
			//char[] c=nextToken().toCharArray();
            ArrayList<Integer> i1=new ArrayList<Integer>();
            ArrayList<Integer> i2=new ArrayList<Integer>();
            ArrayList<Integer> x1=new ArrayList<Integer>();
            ArrayList<Integer> y1=new ArrayList<Integer>();
			int n = nextInt();
			//long n = nextLong();

			int[] a=new int[n];
			//long[] a=new long[n];
			for(int i=0;i<n;i++){
				a[i]=nextInt();
			}
			//shuffle(a);
			//shufflel(a);
			//Arrays.sort(a);
			int k=0;
			int j=0;
			int u=0;
			for(int i=1;i<n;i++){
			    if(gcd(a[i],a[i-1])!=1){
			        k++;
			        
			        int x=Math.min(a[i],a[i-1]);
			        x1.add(x);
			        if(u==0){
			            
    			        y1.add(1000000007);
    			        if(a[i]<a[i-1]){
    			            i1.add(i+1);
			        i2.add(i);
    			            a[i-1]=1000000007;
    			        }
    			        else{
    			            i1.add(i);
			        i2.add(i+1);
    			            a[i]=1000000007;
    			        }
    			        u=1;
			        }
			        else{
			            y1.add(1000000009);
    			        if(a[i]<a[i-1]){
    			            i1.add(i+1);
			        i2.add(i);
    			            a[i-1]=1000000009;
    			        }
    			        else{
    			            i1.add(i);
			        i2.add(i+1);
    			            a[i]=1000000009;
    			        }
    			        u=0;
			        }
			    }
			}
			writer.println(k);
            for(int i=0;i<k;i++){
                writer.print(i1.get(i)+" ");
                writer.print(i2.get(i)+" ");
                writer.print(x1.get(i)+" ");
                writer.println(y1.get(i));
            }
            //for(int i=0;i<n;i++){
          //  writer.println(a[i]);}
			
		 }
	}
}