The 3rd Universal Cup жартылай финалында бірде-бір команда «Queue Editor» есебін шығара алмағанын атап өту үшін, Little Cyan Fish кезекке және... бұл жолы стекке байланысты жаңа есеп ойлап тапты! Онда $1$-ден $n$-ге дейін нөмірленген $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$.