import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class F implements Runnable {

    final boolean LOCAL = new File("C:/Windows/System32/drivers/etc/hosts").exists();
    final String PROBLEM_NAME = getClass().getSimpleName().toLowerCase();

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok;

    public static void main(String[] args) {
        new Thread(null, new F(), "", 256 * (1L << 20)).start();
    }

    @Override
    public void run() {
        try {
            long startTime = 0, endTime = 0;
            long freeMemory = 0, totalMemory = 0;
            if (LOCAL) {
                startTime = System.currentTimeMillis();
            }
            Locale.setDefault(Locale.US);
            if (LOCAL) {
                in = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            } else {
//              in = new BufferedReader(new FileReader(PROBLEM_NAME + ".in"));
//              out = new PrintWriter(PROBLEM_NAME + ".out");
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
//              in = new BufferedReader(new FileReader("input.txt"));
//              out = new PrintWriter("output.txt");
            }
            tok = new StringTokenizer("");
            solve();
            in.close();
            out.close();
            if (LOCAL) {
                endTime = System.currentTimeMillis();
                freeMemory = Runtime.getRuntime().freeMemory();
                totalMemory = Runtime.getRuntime().totalMemory();
            }
            if (LOCAL) {
                System.err.println("Time = " + (endTime - startTime));
                System.err.println("Memory = " + ((totalMemory - freeMemory) >> 10));
            }
        } catch (Throwable t) {
            t.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            String line = in.readLine();
            if (line == null) return null;
            tok = new StringTokenizer(line);
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    void debug(Object... o) {
        if (LOCAL) {
            System.err.println(Arrays.deepToString(o));
        }
    }

    // solution

    int n;
    int[] a = new int[100000];
    int[] heapIds = new int[10000005];
    int[] heapValues = new int[10000005];
    int size;
    long ans;

    void update(int i, int x) {
        if (i < 0 || i >= n) return;
        if (a[i] <= x) return;
        ans += a[i] - x;
        a[i] = x;
        push(a[i], i);
    }

    void solve() throws IOException {
        int T = readInt();
        for (int t = 1; t <= T; t++) {
            size = 0;
            n = readInt();
            for (int i = 0; i < n; i++) {
                a[i] = readInt();
                push(a[i], i);
            }
            ans = 0;
            while (size > 0) {
                int x = heapValues[1];
                int i = heapIds[1];
                pop();
                if (a[i] != x) continue;
                update(i-1, x+1);
                update(i+1, x+1);
            }
            out.println(ans);
        }
    }

    private void pop() {
        heapValues[1] = heapValues[size];
        heapIds[1] = heapIds[size];
        size--;
        int k = 1;
        while (true) {
            int minK = k;
            if (2*k <= size) {
                if (heapValues[2*k] < heapValues[minK]) {
                    minK = 2*k;
                }
            }
            if (2*k+1 <= size) {
                if (heapValues[2*k+1] < heapValues[minK]) {
                    minK = 2*k+1;
                }
            }
            if (minK == k) {
                break;
            }
            swap(k, minK);
            k = minK;
        }
    }

    private void swap(int i, int j) {
        int t = heapIds[i]; heapIds[i] = heapIds[j]; heapIds[j] = t;
        t = heapValues[i]; heapValues[i] = heapValues[j]; heapValues[j] = t;
    }

    private void push(int x, int i) {
        size++;
        heapIds[size] = i;
        heapValues[size] = x;
        int k = size;
        while (k > 1) {
            if (heapValues[k] >= heapValues[k / 2]) {
                break;
            }
            swap(k, k/2);
            k /= 2;
        }
    }

}