גביע מרובי-הראשים (Multi-Heads Cup, או בקיצור MHC) הוא תחרות תכנות עולמית שנוצרה עבור משתתפים עם המון המון ראשים. בשנת 2023, השופט הראשי של אירוע זה, Little Cyan Fish, פתר בעיית אימות מסובכת באמצעות סוגים רבים של סוגריים.

זו הייתה הפעם הראשונה שבה Little Cyan Fish ראה מתחרים עם המון המון ראשים. והפעם, Little Cyan Fish מביא בעיית סוגריים נוספת לחברו הטוב ביותר שיש לו המון המון ראשים. ל-Little Cyan Fish יש $n$ סוגים של סוגריים בידו, וכל סוג של סוגריים מתחלק לסוגריים שמאליים (פותחים) ולסוגריים ימניים (סוגרים). לנוחותנו, נשתמש ב-$L^i$ כדי לסמן את הסוג ה-$i$ של סוגר שמאלי, וב-$R^i$ כדי לסמן את הסוג ה-$i$ של סוגר ימני.

"היי, אל תשכח," חשב Little Cyan Fish, "כבר הצגתי בפניך בעבר מהי סדרת סוגריים מאוזנת!" כדי להבטיח שאתה מבין את המושג של סדרת סוגריים מאוזנת, Little Cyan Fish הכין את ההגדרה הפורמלית הבאה של סדרת סוגריים מאוזנת:

• $\varepsilon$ (מחרוזת ריקה) היא סדרת סוגריים מאוזנת.
• אם $A$ היא סדרת סוגריים מאוזנת, אזי גם $(A)$ היא סדרת סוגריים מאוזנת.
• אם $A$ ו-$B$ הן סדרות סוגריים מאוזנות, אזי גם $AB$ היא סדרת סוגריים מאוזנת.

לדוגמה, "()", "()()" ו-"(())" הן סדרות סוגריים מאוזנות, אך ")(", "(" ו-"))" אינן כאלה.

כעת, Little Cyan Fish נותן לך סדרת סוגריים $S$ באורך $n$, המכילה $n$ סוגים של סוגריים. למרבה הצער, Little Cyan Fish שכח את סוגי הסוגריים בחלק מהמיקומים, וגם שכח את כיווני הסוגריים במיקומים אלה. הזיכרון של מיקומים אלה הפך מטושטש ומיוצג על ידי ? אצל Little Cyan Fish.

Little Cyan Fish סקרן מאוד לדעת, עבור כל $1 \le l \le r \le n$, כמה זוגות $(l, r)$ מתאימים לתתי-מחרוזות $S[l \dots r]$, כך שקיימת דרך למלא את ? בסוג כלשהו של סוגר בכיוון כלשהו, כך שעבור כל $1 \le i \le n$ מתקיים:

• אם מחלצים את כל הסוגריים מסוג $i$ (כלומר את כל $L^i$ ו-$R^i$), סדרת הסוגריים המתקבלת (המכילה רק את הסוג ה-$i$ של סוגריים) היא סדרת סוגריים מאוזנת.

לדוגמה, אם נשתמש ב-"()" כדי לסמן את הסוג הראשון של סוגריים וב-"[]" כדי לסמן את הסוג השני של סוגריים, מחרוזת הסוגריים ([?) מקיימת את התנאי לעיל, משום שנוכל להחליף את ? ב-]. גם (?)] מקיימת את התנאי לעיל, משום שנוכל להחליף את ? ב-[.

Little Cyan Fish רוצה שתחשב את מספר כל הזוגות החוקיים $(l, r)$.

קלט

ישנם מספר מקרי בדיקה. השורה הראשונה של הקלט מכילה מספר שלם בודד $T$ ($1 \le T$), המציין את מספר מקרי הבדיקה.

עבור כל מקרה בדיקה, השורה הראשונה של הקלט מכילה מספר שלם $n$ ($1 \le n \le 2 \times 10^5$), המציין את אורך מחרוזת הסוגריים.

השורה הבאה מכילה $n$ מספרים שלמים $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$). $n$ מספרים שלמים אלה מתארים את המידע של מחרוזת הסוגריים, כאשר:

• אם $x_i > 0$, אזי המיקום ה-$i$ מייצג את הסוג ה-$x_i$ של סוגר שמאלי (כלומר $L^{x_i}$).
• אם $x_i < 0$, אזי המיקום ה-$i$ מייצג את הסוג ה-$-x_i$ של סוגר ימני (כלומר $R^{-x_i}$).
• אם $x_i = 0$, פירוש הדבר ש-Little Cyan Fish שכח את המידע במיקום זה (כלומר ?).

מובטח כי סכום ערכי $n$ על פני כל מקרי הבדיקה אינו עולה על $2 \times 10^5$.

פלט

עבור כל מקרה בדיקה, הדפס שורה אחת המכילה מספר שלם אחד, המציין את התשובה.

דוגמה

קלט 1

4
4
1 2 -1 -2
4
1 0 -2 0
6
1 2 3 -3 -2 -1
8
1 0 0 3 0 0 0 -2

פלט 1

1
3
3
14