احتفالًا بحقيقة أنه لم يتمكن أي فريق من حل مسألة «Queue Editor» في نصف نهائي البطولة العالمية الثالثة (The 3rd Universal Cup Semifinals)، ابتكر Little Cyan Fish مسألة جديدة تتضمن طابورًا و... هذه المرة، مكدسًا (stack)! لديه $n$ كرات مرقمة من $1$ إلى $n$. الكرات مرتبة في البداية داخل طابور، ولديه أيضًا مكدس فارغ. طالما أن الطابور غير فارغ، فإنه ينفذ الخطوات التالية:

1. إزالة الكرة الموجودة في مقدمة الطابور. ليكن رقمها $x$.
2. طالما أن المكدس غير فارغ ورقم الكرة الموجودة في قمته أكبر من $x$، قم بإزالة الكرة من قمة المكدس وإضافتها إلى نهاية الطابور. تُضاف الكرات بنفس الترتيب الذي تُزال به.
3. دفع الكرة ذات الرقم $x$ إلى قمة المكدس.

يمكن إثبات أن الطابور يصبح فارغًا بعد عدد منتهٍ من الخطوات. أوجد إجمالي عدد المرات التي يدفع فيها Little Cyan Fish كرة إلى المكدس قبل حدوث ذلك.

الإدخال

توجد عدة حالات اختبار. يحتوي السطر الأول من الإدخال على عدد صحيح واحد $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$.