You are given an array a consisting of n positive integers, numbered from 1 to n. You can perform the following operation no more than 3n times:

  1. choose three integers i, j and x (1 ≤ i, j ≤ n; 0 ≤ x ≤ 10^9); 
  2. assign a_i := a_i - x ⋅ i, a_j := a_j + x ⋅ i. 



After each operation, all elements of the array should be non-negative.

Can you find a sequence of no more than 3n operations after which all elements of the array are equal?

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 10^4) — the number of elements in the array. The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^5) — the elements of the array.

It is guaranteed that the sum of n over all test cases does not exceed 10^4.

Output

For each test case print the answer to it as follows:

  * if there is no suitable sequence of operations, print -1; 
  * otherwise, print one integer k (0 ≤ k ≤ 3n) — the number of operations in the sequence. Then print k lines, the m-th of which should contain three integers i, j and x (1 ≤ i, j ≤ n; 0 ≤ x ≤ 10^9) for the m-th operation. 



If there are multiple suitable sequences of operations, print any of them. Note that you don't have to minimize k.

Example

Input


3
4
2 16 4 18
6
1 2 3 4 5 6
5
11 19 1 1 3


Output


2
4 1 2
2 3 3
-1
4
1 2 4
2 4 5
2 3 3
4 5 1
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class D {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            solve(sc, pw);
        }
        pw.close();
    }
    static void solve(Scanner in, PrintWriter out){
        int n = in.nextInt();
        long[] arr = new long[n];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            cnt += arr[i];
        }
        if (cnt % n != 0){
            out.println(-1);
            return;
        }
        List<long[]> res = new ArrayList<>();
        int tar = cnt / n;
        for (int i = 1; i < n; i++) {
            int div = i + 1;
            if (arr[i] % div == 0){
//                out.println(div+" "+1+" "+(arr[i] / div));
                res.add(new long[]{div, 1, (arr[i] / div)});
            }else{
                long dis = 0;
                if (arr[i] < div){
                    dis = div - arr[i];
                }else{
                    dis = (div - (arr[i] % div));
                }
//                out.println(1+" "+div+" "+(dis));
                res.add(new long[]{1, div, dis});
//                out.println(div+" "+1+" "+(arr[i] + dis) / div);
                res.add(new long[]{div, 1, (arr[i] + dis) / div});
            }
        }
        for (int i = 1; i < n; i++) {
//            out.println(1+" "+(i + 1)+" "+tar);
            res.add(new long[]{1, i + 1, tar});
        }
        out.println(res.size());
        for(long[] ok : res){
            out.println(ok[0]+" "+ok[1]+" "+ok[2]);
        }
    }

    static boolean isPrime(long n)
    {
        // Corner cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;

        // This is checked so that we can skip
        // middle five numbers in below loop
        if (n % 2 == 0 || n % 3 == 0)
            return false;

        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;

        return true;
    }

    static long gcd(long a, long b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }

    // method to return LCM of two numbers
    static long lcm(long a, long b)
    {
        return (a / gcd(a, b)) * b;
    }

    public static int[] sieveEratosthenes(int n) {
        if (n <= 32) {
            int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
            for (int i = 0; i < primes.length; i++) {
                if (n < primes[i]) {
                    return Arrays.copyOf(primes, i);
                }
            }
            return primes;
        }

        int u = n + 32;
        double lu = Math.log(u);
        int[] ret = new int[(int) (u / lu + u / lu / lu * 1.5)];
        ret[0] = 2;
        int pos = 1;

        int[] isnp = new int[(n + 1) / 32 / 2 + 1];
        int sup = (n + 1) / 32 / 2 + 1;

        int[] tprimes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
        for (int tp : tprimes) {
            ret[pos++] = tp;
            int[] ptn = new int[tp];
            for (int i = (tp - 3) / 2; i < tp << 5; i += tp) ptn[i >> 5] |= 1 << (i & 31);
            for (int j = 0; j < sup; j += tp) {
                for (int i = 0; i < tp && i + j < sup; i++) {
                    isnp[j + i] |= ptn[i];
                }
            }
        }

        // 3,5,7
        // 2x+3=n
        int[] magic = {0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14};
        int h = n / 2;
        for (int i = 0; i < sup; i++) {
            for (int j = ~isnp[i]; j != 0; j &= j - 1) {
                int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27];
                int p = 2 * pp + 3;
                if (p > n) break;
                ret[pos++] = p;
                if ((long) p * p > n) continue;
                for (int q = (p * p - 3) / 2; q <= h; q += p) isnp[q >> 5] |= 1 << q;
            }
        }

        return Arrays.copyOf(ret, pos);
    }

    //    reverse division for 2
    public static long[] rdiv2(int n, int mod){
        long[] arr = new long[n + 5];
        arr[0] = 1;
        long rev2 = (mod + 1) / 2;
        for (int i = 1; i < n; i++) {
            arr[i] = arr[i - 1] * rev2 % mod;
        }
        return arr;
    }
    static List<Integer> primeFactors(int n)
    {
        // Print the number of 2s that divide n
        List<Integer> ls = new ArrayList<>();
        if (n % 2 == 0) ls.add(2);
        while (n%2==0)
        {
            n /= 2;
        }

        // n must be odd at this point.  So we can
        // skip one element (Note i = i +2)
        for (int i = 3; i <= Math.sqrt(n); i+= 2)
        {
            // While i divides n, print i and divide n
            if (n  % i == 0) ls.add(i);
            while (n%i == 0)
            {
                n /= i;
            }
        }
        if (n > 1) ls.add(n);
        return ls;
    }

    static int find(int i, int[] par){
        if (par[i] < 0) return i;
        return par[i] = find(par[i], par);
    }
    static boolean union(int i, int j, int[] par){
        int pi = find(i, par);
        int pj = find(j, par);
        if (pi == pj) return false;
        if (par[pi] < par[pj]){
            par[pi] += par[pj];
            par[pj] = pi;
        }else{
            par[pj] += par[pi];
            par[pi] = pj;
        }
        return true;
    }
}
