为了庆祝在第三届 Universal Cup 半决赛中没有队伍通过“队列编辑器”（Queue Editor）一题，小青鱼想出了一道关于队列以及……这一次还有栈的新题目！他有 $n$ 个编号从 $1$ 到 $n$ 的球。这些球最初排列在一个队列中，同时他还有一个空栈。当队列非空时，他会执行以下步骤：

1. 移除队首的球。设其编号为 $x$。
2. 当栈非空且栈顶球的编号大于 $x$ 时，移除栈顶的球并将其追加到队尾。各球按其被移除的先后顺序依次追加到队尾。
3. 将编号为 $x$ 的球压入栈顶。

可以证明，经过有限步后队列一定会变为空。求在此之前小青鱼将球压入栈中的总次数。

输入格式

本题包含多组测试数据。输入的第一行包含一个整数 $T$（$1 \le T$），表示测试数据的组数。

对于每组测试数据，第一行包含一个整数 $n$（$1 \le n \le 5 \times 10^5$），表示球的数量。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示初始队列中从队首到队尾各个球的编号。保证 $a_1, a_2, \ldots, a_n$ 构成 $1, 2, \ldots, n$ 的一个排列。

保证所有测试数据中 $n$ 的总和不超过 $5 \times 10^5$。

输出格式

对于每组测试数据，输出一行一个整数，表示球被压入栈中的总次数。

样例

输入格式 1

4
1
1
3
1 2 3
3
2 1 3
3
3 1 2

输出格式 1

1
3
5
4

输入格式 2

2
3
2 3 1
6
1 3 4 6 2 5

输出格式 2

6
15

说明

在第一个样例中，四组测试数据里被压入栈中的球编号序列分别为 $(1)$、$(1, 2, 3)$、$(2, 1, 3, 2, 3)$ 和 $(3, 1, 2, 3)$。题目描述中的图示展示了第一个样例中的第三组测试数据。

在第二个样例的第一组测试数据中，被压入栈中的球编号序列为 $(2, 3, 1, 3, 2, 3)$，因此答案为 $6$。在第二个样例的第二组测试数据中，该序列为 $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$，因此答案为 $15$。