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.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        MyReader reader = new MyReader(System.in);
//        MyReader reader = new MyReader(new FileInputStream("input.txt"));
        MyWriter writer = new MyWriter(System.out);
        new Main().run(reader, writer);
        writer.close();
    }

    private void run(MyReader reader, MyWriter writer) throws Exception {
        int t = reader.nextInt();
        la:
        for (int i = 0; i < t; i++) {
            int n = reader.nextInt();
            int[] a = reader.nextIntArray(n);
            int sum = 0;
            for (int j = 0; j < n; j++) {
                sum += a[j];
            }
            if (sum % n != 0) {
                writer.println(-1);
                continue;
            }
            int b = sum / n;
            List<Triple<Integer>> list = new ArrayList<>();
            for (int j = 1; j < n; j++) {
                int q = a[j] % (j + 1);
                q = (j + 1 - q) % (j + 1);
                list.add(new Triple<>(1, j + 1, q));
                a[j] += q;
                list.add(new Triple<>(j + 1, 1, a[j] / (j + 1)));
            }
            for (int j = 1; j < n; j++) {
                list.add(new Triple<>(1, j + 1, b));
            }
            writer.println(list.size());
            for (Triple<Integer> e : list) {
                writer.println(e.x + " " + e.y + " " + e.z);
            }
        }
    }

    class Pair<T> extends Pair2<T, T> {

        public Pair(T x, T y) {
            super(x, y);
        }
    }

    class Pair2<T, U> {

        T x;
        U y;

        public Pair2(T x, U y) {
            this.x = x;
            this.y = y;
        }
    }

    class Triple<T> {
        T x;
        T y;
        T z;

        public Triple(T x, T y, T z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }

    public class DSU {

        int n;
        int[] p;
        int[] r;

        DSU(int n) {
            this.n = n;
            p = new int[n];
            for (int i = 0; i < n; i++) {
                p[i] = i;
            }
            r = new int[n];
        }

        int get(int x) {
            if (p[x] != x) {
                p[x] = get(p[x]);
            }
            return p[x];
        }

        void union(int x, int y) {
            x = get(x);
            y = get(y);
            if (x == y) {
                return;
            }
            if (r[x] == r[y]) {
                r[x]++;
            }
            if (r[x] < r[y]) {
                p[x] = y;
            } else {
                p[y] = x;
            }
        }
    }

    public class Graph<T> {

        int counter = 0;
        List<Node> nodes = new ArrayList<>();
        List<Long> dist;

        void initNodes(int n) {
            for (int i = 0; i < n; i++) {
                nodes.add(new Node());
            }
        }

        void addNode(T obj) {
            nodes.add(new Node(obj));
        }

        void addEdge(int i, int j, boolean oriented) {
            addEdge(i, j, 0, oriented);
        }

        void addEdge(int i, int j, long w, boolean oriented) {
            Node from = nodes.get(i);
            Node to = nodes.get(j);
            addEdge(from, to, w, oriented);
        }

        void addEdge(Node from, Node to, boolean oriented) {
            addEdge(from, to, 0, oriented);
        }

        void addEdge(Node from, Node to, long w, boolean oriented) {
            Edge edge = new Edge(from, to, w);
            from.edges.add(edge);
            if (!oriented) {
                Edge rev = new Edge(to, from, w);
                to.edges.add(rev);
            }
        }

        long mst() {
            List<Edge> list = new ArrayList<>();
            for (Node node : nodes) {
                list.addAll(node.edges);
            }
            list.sort((e1, e2) -> (int) (e1.w - e2.w));
            DSU dsu = new DSU(nodes.size());
            long weight = 0;
            for (Edge edge : list) {
                if (dsu.get(edge.from.i) != dsu.get(edge.to.i)) {
                    weight += edge.w;
                    dsu.union(edge.from.i, edge.to.i);
                }
            }
            return weight;
        }

//    void dijkstra() {
//        PriorityQueue<Main.Pair2<Node, Long>> queue = new PriorityQueue<>((o1, o2) -> (int) (o1.y - o2.y));
//        queue.add(new Main.Pair2<>(nodes.get(0), 0L));
//        while (!queue.isEmpty()) {
//            Main.Pair2<Node, Long> p = queue.poll();
//            Node n = p.x;
//            long d = p.y;
//            if (n.dist != -1) {
//                continue;
//            }
//            n.dist = d;
//            for (Edge edge : n.edges) {
//                queue.add(new Main.Pair2<>(edge.to, d + edge.w));
//            }
//        }
//    }

        class Node {

            int i;
            T obj;
            List<Edge> edges = new ArrayList<>();
            long dist = -1;

            public Node() {
                this(null);
            }

            public Node(T obj) {
                this.i = counter++;
                this.obj = obj;
            }
        }

        class Edge {

            long w;
            Node from;
            Node to;

            public Edge(Node from, Node to) {
                this(from, to, 0);
            }

            public Edge(Node from, Node to, long w) {
                this.from = from;
                this.to = to;
                this.w = w;
            }
        }
    }


    public static class MyReader {

        final BufferedInputStream in;
        final int bufSize = 1 << 16;
        final byte[] buf = new byte[bufSize];
        int i = bufSize;
        int k = bufSize;
        boolean end = false;
        final StringBuilder str = new StringBuilder();

        MyReader(InputStream in) {
            this.in = new BufferedInputStream(in, bufSize);
        }

        int nextInt() throws IOException {
            return (int) nextLong();
        }

        int[] nextIntArray(int n) throws IOException {
            int[] m = new int[n];
            for (int i = 0; i < n; i++) {
                m[i] = nextInt();
            }
            return m;
        }

        int[][] nextIntMatrix(int n, int m) throws IOException {
            int[][] a = new int[n][0];
            for (int j = 0; j < n; j++) {
                a[j] = nextIntArray(m);
            }
            return a;
        }

        long nextLong() throws IOException {
            int c;
            long x = 0;
            int sign = 1;
            while ((c = nextChar()) <= 32) ;
            if (c == '-') {
                sign = -1;
                c = nextChar();
            }
            if (c == '+') {
                c = nextChar();
            }
            while (c >= '0') {
                x = x * 10 + (c - '0');
                c = nextChar();
            }
            return sign * x;
        }

        long[] nextLongArray(int n) throws IOException {
            long[] m = new long[n];
            for (int i = 0; i < n; i++) {
                m[i] = nextLong();
            }
            return m;
        }

        int nextChar() throws IOException {
            if (i == k) {
                k = in.read(buf, 0, bufSize);
                i = 0;
            }
            return i >= k ? -1 : buf[i++];
        }

        String nextString() throws IOException {
            if (end) {
                return null;
            }
            str.setLength(0);
            int c;
            while ((c = nextChar()) <= 32 && c != -1) ;
            if (c == -1) {
                end = true;
                return null;
            }
            while (c > 32) {
                str.append((char) c);
                c = nextChar();
            }
            return str.toString();
        }

        String nextLine() throws IOException {
            if (end) {
                return null;
            }
            str.setLength(0);
            int c = nextChar();
            while (c != '\n' && c != '\r' && c != -1) {
                str.append((char) c);
                c = nextChar();
            }
            if (c == -1) {
                end = true;
                if (str.length() == 0) {
                    return null;
                }
            }
            if (c == '\r') {
                nextChar();
            }
            return str.toString();
        }

        char[] nextCharArray() throws IOException {
            return nextString().toCharArray();
        }

        char[][] nextCharMatrix(int n) throws IOException {
            char[][] a = new char[n][0];
            for (int i = 0; i < n; i++) {
                a[i] = nextCharArray();
            }
            return a;
        }
    }

    public static class MyWriter {

        final BufferedOutputStream out;
        final int bufSize = 1 << 16;
        final byte buf[] = new byte[bufSize];
        int i = 0;
        final byte c[] = new byte[30];
        static final String newLine = System.getProperty("line.separator");

        MyWriter(OutputStream out) {
            this.out = new BufferedOutputStream(out, bufSize);
        }

        void print(long x) throws IOException {
            int j = 0;
            if (i + 30 >= bufSize) {
                flush();
            }
            if (x < 0) {
                buf[i++] = (byte) ('-');
                x = -x;
            }
            do {
                c[j++] = (byte) (x % 10 + '0');
                x /= 10;
            } while (x != 0);
            while (--j >= 0) {
                buf[i++] = c[j];
            }
        }

        void println(long x) throws IOException {
            print(x);
            println();
        }

        void print(int[] m) throws IOException {
            for (int a : m) {
                print(a);
                print(' ');
            }
        }

        void print(long[] m) throws IOException {
            for (long a : m) {
                print(a);
                print(' ');
            }
        }

        void print(String s) throws IOException {
            for (int i = 0; i < s.length(); i++) {
                print(s.charAt(i));
            }
        }

        void print(char x) throws IOException {
            if (i == bufSize) {
                flush();
            }
            buf[i++] = (byte) x;
        }

        void print(char[] m) throws IOException {
            for (char c : m) {
                print(c);
            }
        }

        void println(String s) throws IOException {
            print(s);
            println();
        }

        void println() throws IOException {
            print(newLine);
        }

        void flush() throws IOException {
            out.write(buf, 0, i);
            out.flush();
            i = 0;
        }

        void close() throws IOException {
            flush();
            out.close();
        }
    }
}