import java.io.*;
public class Solution {

    public static void main(String[] args) throws IOException {
        in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        int T = nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = nextInt();
            for (int i = 0; i < N; i++) d[i] = nextInt();

            idx = 0;
            for (int i = 0; i < N; i++) ans += addQue(d[i]);
            idx = 0;
            for (int i = N - 1; i >= 0; i--) ans += addQue(d[i]);

            System.out.println("#" + tc + " " + ans);
        }
    }

    static int addQue(int n) {//单调递减队列
        int ret = idx;
        while (idx > 0 && que[idx] < n) idx--;
        que[++idx] = n;
        return ret;
    }

    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static StreamTokenizer in;
    static int N, idx;
    static long ans;
    static final int[] d = new int[300003];
    static final int[] que = new int[300003];
}