Multi-Heads Cup, немесе қысқаша MHC — бұл көп-көп басы бар қатысушыларға арналған дүниежүзілік бағдарламалау сайысы. 2023 жылы осы жарыстың бас төрешісі Little Cyan Fish жақшалардың көптеген түрлерін пайдаланып, күрделі аутентификация есебін шешті.

Бұл Little Cyan Fish-тің көп-көп басы бар қатысушыларды алғаш рет көруі еді. Ал бұл жолы Little Cyan Fish өзінің көп-көп басы бар ең жақын досына жақшалар туралы тағы бір есеп алып келді. Little Cyan Fish-тің қолында $n$ түрлі жақша бар, және жақшаның әрбір түрі сол жақ (ашылатын) және оң жақ (жабылатын) жақшаларға бөлінеді. Ыңғайлы болу үшін сол жақ жақшаның $i$-ші түрін белгілеу үшін $L^i$, ал оң жақ жақшаның $i$-ші түрін белгілеу үшін $R^i$ қолданамыз.

«Ей, ұмытпа, — деп ойлады Little Cyan Fish, — мен саған бұрын дұрыс жақша тізбегі деген не екенін таныстырғанмын!» Сіздің дұрыс жақша тізбегі ұғымын нақты түсінгеніңізге көз жеткізу үшін Little Cyan Fish дұрыс жақша тізбегінің келесі формалды анықтамасын дайындады:

• $\varepsilon$ (бос жол) — дұрыс жақша тізбегі.
• Егер $A$ дұрыс жақша тізбегі болса, онда $(A)$ да дұрыс жақша тізбегі болады.
• Егер $A$ және $B$ дұрыс жақша тізбектері болса, онда $AB$ де дұрыс жақша тізбегі болады.

Мысалы, «()», «()()» және «(())» — дұрыс жақша тізбектері, бірақ «)(», «(» және «))» олай емес.

Енді Little Cyan Fish сізге жақшаның $n$ түрін қамтитын ұзындығы $n$ болатын $S$ жақша тізбегін береді. Өкінішке орай, Little Cyan Fish кейбір орындардағы жақшалардың түрлерін ұмытып қалды, сондай-ақ сол орындардағы жақшалардың бағыттарын да ұмытып қалды. Бұл орындар туралы естеліктер бұлдырап, оларды Little Cyan Fish ? таңбасымен белгіледі.

Little Cyan Fish-ті барлық $1 \le l \le r \le n$ үшін $S[l \dots r]$ ішкі жолдарына сәйкес келетін қанша $(l, 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