Щоб відсвяткувати той факт, що жодна команда не розв'язала задачу «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$.