An important meeting is to be held and there are exactly n people invited. At any moment, any two people can step back and talk in private. The same two people can talk several (as many as they want) times per meeting.

Each person has limited sociability. The sociability of the i-th person is a non-negative integer a_i. This means that after exactly a_i talks this person leaves the meeting (and does not talk to anyone else anymore). If a_i = 0, the i-th person leaves the meeting immediately after it starts.

A meeting is considered most productive if the maximum possible number of talks took place during it.

You are given an array of sociability a, determine which people should talk to each other so that the total number of talks is as large as possible.

Input

The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases.

The next 2t lines contain descriptions of the test cases.

The first line of each test case description contains an integer n (2 ≤ n ≤ 2 ⋅ 10^5) —the number of people in the meeting. The second line consists of n space-separated integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 2 ⋅ 10^5) — the sociability parameters of all people. 

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5. It is also guaranteed that the sum of all a_i (over all test cases and all i) does not exceed 2 ⋅ 10^5.

Output

Print t answers to all test cases.

On the first line of each answer print the number k — the maximum number of talks possible in a meeting.

On each of the next k lines print two integers i and j (1 ≤ i, j ≤ n and i ≠ j) — the numbers of people who will have another talk.

If there are several possible answers, you may print any of them.

Example

Input


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


Output


2
1 2
1 2
3
1 3
2 3
2 3
5
1 3
2 4
2 4
3 4
3 4
0
2
1 2
1 2
0
4
1 2
1 5
1 4
1 2
1
5 2
/*
+-------------------------------+
| Written by Kabir Kanha Arora. |
|   @kabirkanha  |    @Kabir    |
+-------------------------------+
 */

import java.io.*;
import java.util.*;

public class Main {

    static long[] fact;
    static boolean[] visited;
    static ArrayList<ArrayList<Pair>> adjList;
    static int[][] shortestDistance;
    static FastScanner scanner = new FastScanner();
    static PrintWriter out = new PrintWriter(System.out);

    static long MOD = 1000000007;

    public static void main(String[] args) {
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt();
            Pair[] pairs = new Pair[n];
            for (int i = 0; i < n; ++i) {
                pairs[i] = new Pair(i + 1, scanner.nextInt());
            }
            Arrays.sort(pairs, (o1, o2) -> Integer.compare(o1.second, o2.second));
            ArrayList<Integer> list = new ArrayList<>();
            int sum = 0;
            for (int i = 0; i < n; ++i) {
                Pair pair = pairs[i];
                for (int cnt = 0; cnt < pair.second; ++cnt) {
                    list.add(pair.first);
                }
                sum += pair.second;
            }
            if (pairs[n - 1].second > sum / 2) {
                out.println(sum - pairs[n - 1].second);
            } else {
                out.println(sum / 2);
            }
            int l = 0;
            int r = list.size() / 2;
            while (list.get(l) != pairs[n - 1].first && r < list.size() && l < list.size() / 2) {
                out.println(list.get(l) + " " + list.get(r));
                ++l;
                ++r;
            }
        }
        out.close();
    }

    /*
    +--------------------------------------------+
    | METHODS BELOW THIS LINE ARE TEMPLATE CODE. |
    +--------------------------------------------+
     */

    // Shuffle and sort array
    static void shuffleAndSort(int[] arr) {
        for (int i = 0; i < arr.length; ++i) {
            int random_index = (int) (Math.random() * arr.length);
            int temp = arr[i];
            arr[i] = arr[random_index];
            arr[random_index] = temp;
        }
        Arrays.sort(arr);
    }

    // Pair class
    static class Pair {
        int first;
        int second;

        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

    // Sort array of pairs in asc order by first elem
    static void sortPairByFirst(Pair[] arr) {
        Arrays.sort(arr, Comparator.comparingInt(o -> o.first));
    }

    // Sort array of pairs in asc order by second elem
    static void sortPairBySecond(Pair[] arr) {
        Arrays.sort(arr, Comparator.comparingInt(o -> o.second));
    }

    // Triplet class
    static class Triplet {
        int first;
        int second;
        int third;

        Triplet(int first, int second, int third) {
            this.first = first;
            this.second = second;
            this.third = third;
        }
    }

    // Swap two elements of an int array
    static void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

    // Swap two elements of a String array
    static void swap(String[] arr, int left, int right) {
        String temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

    // Reverse an int subarray
    static void reverse(int[] arr, int left, int right) {
        while (left < right) {
            swap(arr, left++, right--);
        }
    }

    // Reverse a String subarray
    static void reverse(String[] arr, int left, int right) {
        while (left < right) {
            swap(arr, left++, right--);
        }
    }

    // Binary search to find the first element >= num
    // a.k.a lower_bound()
    static int atLeastN(int[] arr, int start, int end, int num) {
        if (arr[end] < num)
            return -1;
        while (start < end) {
            int mid = (start + end) / 2;
            if (arr[mid] < num)
                start = mid + 1;
            else
                end = mid;
        }
        return start;
    }

    // Binary search to find the last element <= num
    static int atMostN(int[] arr, int start, int end, int num) {
        if (arr[start] > num)
            return -1;
        while (start < end) {
            int mid = (start + end + 1) / 2;
            if (arr[mid] > num)
                end = mid - 1;
            else
                start = mid;
        }
        return start;
    }

    // Find next permutation of an int array
    public static boolean nextPermutation(int[] arr) {
        if (arr.length <= 1)
            return false;
        int last = arr.length - 2;

        // Find longest non-increasing suffix and pivot
        while (last >= 0) {
            if (arr[last] < arr[last + 1]) {
                break;
            }
            last--;
        }

        // No increasing pair found
        if (last < 0)
            return false;

        // Find the rightmost successor to the pivot
        int nextGreater = arr.length - 1;
        for (int i = arr.length - 1; i > last; i--) {
            if (arr[i] > arr[last]) {
                nextGreater = i;
                break;
            }
        }

        // Swap the successor and the pivot
        swap(arr, nextGreater, last);
        // Reverse the suffix
        reverse(arr, last + 1, arr.length - 1);
        // Found next_permutation
        return true;
    }

    // Find next permutation of a String array
    public static boolean nextPermutation(String[] arr) {
        if (arr.length <= 1)
            return false;
        int last = arr.length - 2;

        // Find longest non-increasing suffix and pivot
        while (last >= 0) {
            if (arr[last].compareTo(arr[last + 1]) < 0) {
                break;
            }
            last--;
        }

        // No increasing pair found
        if (last < 0)
            return false;

        // Find the rightmost successor to the pivot
        int nextGreater = arr.length - 1;
        for (int i = arr.length - 1; i > last; i--) {
            if (arr[i].compareTo(arr[last]) > 0) {
                nextGreater = i;
                break;
            }
        }

        // Swap the successor and the pivot
        swap(arr, nextGreater, last);
        // Reverse the suffix
        reverse(arr, last + 1, arr.length - 1);
        // Found next_permutation
        return true;
    }

    // Compute Factorials
    static void preComputeFactorials(int SIZE) {
        fact = new long[SIZE + 1];
        fact[0] = 1;
        fact[1] = 1;
        for (int i = 2; i <= SIZE; ++i)
            fact[i] = i * fact[i - 1];
    }

    // Combinations
    static long nCr(int n, int r) {
        if (n < r)
            return 0;
        return (fact[n] * ((inv(fact[r]) * inv(fact[n - r])) % MOD)) % MOD;
    }

    // Modular inverse
    static long inv(long x) {
        return power(x, MOD - 2);
    }

    // Binary exponentiation
    static long power(long x, long y) {
        long res = 1;
        x %= MOD;
        while (y > 0) {
            if (y % 2 == 1)
                res = (res * x) % MOD;
            y = y >> 1;
            x = (x * x) % MOD;
        }
        return res;
    }

    // Create adjacency lists for graph
    static void createAdjLists(int n, boolean weighted, boolean directed) {
        for (int i = 0; i < n; ++i) {
            ArrayList<Pair> temp = new ArrayList<>();
            adjList.add(temp);
        }
        for (int i = 0; i < n - 1; ++i) {
            int v1 = scanner.nextInt() - 1;
            int v2 = scanner.nextInt() - 1;
            int weight = weighted ? scanner.nextInt() : 0;
            adjList.get(v1).add(new Pair(v2, weight));
            if (!directed)
                adjList.get(v2).add(new Pair(v1, weight));
        }
    }

    // DFS
    static void dfs(int root) {
        visited[root] = true;
        out.println(root);
        for (Pair pair : adjList.get(root)) {
            int node = pair.first;
            int weight = pair.second;
            if (!visited[node]) {
                dfs(node);
            }
        }
    }

    // Floyd-Warshall Algorithm - O(V^3)
    static void floydWarshall() {
        int V = shortestDistance.length;
        for (int i = 0; i < V; ++i)
            shortestDistance[i][i] = 0;
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (shortestDistance[i][k] != -1 && shortestDistance[k][j] != -1) {
                        if ((shortestDistance[i][k] + shortestDistance[k][j] < shortestDistance[i][j]) || (shortestDistance[i][j] == -1)) {
                            shortestDistance[i][j] = shortestDistance[i][k] + shortestDistance[k][j];
                        }
                    }
                }
            }
        }
    }

    // Check if a string is a palindrome
    static boolean checkPalindrome(String str) {
        StringBuilder str_rev = new StringBuilder(str);
        str_rev.reverse();
        return str.equals(str_rev.toString());
    }

    // Fast IO
    static class FastScanner {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; ++i) a[i] = nextInt();
            return a;
        }

        long[] readLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; ++i) a[i] = nextLong();
            return a;
        }
    }
}

/*
Are you sure you covered all the edge cases?
 */
