Чтобы отпраздновать тот факт, что ни одна команда не решила задачу «Queue Editor» в полуфинале 3-го Universal Cup, Маленькая Циановая Рыбка придумала новую задачу с очередью и... на этот раз со стеком! У него есть $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$.