כדי לחגוג את העובדה שאף קבוצה לא פתרה את הבעיה "Queue Editor" בחצי הגמר של The 3rd Universal Cup, דג הציאן הקטן (Little Cyan Fish) הגה בעיה חדשה הכוללת תור ו... הפעם, מחסנית! יש לו $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$.