Дәстүрлі гомоку немесе қатарынан бес тас ойыны кішкентай тақтада ойналады және бір түсті бес тас бір сызыққа тізілгенде бірден аяқталады. Алайда «Жаңа гомоку» ойынында ережелер басқаша. Жаңа гомоку ережелері келесідей:

• Тақта үлкенірек, оның ұзындығы мен ені $1000$-ға тең.
• Қара және ақ ойыншылар қара ойыншыдан бастап кезекпен өз тастарын қояды. Тас қойылған координатаға қайтадан тас қоюға болмайды.
• Егер бір түсті дәл $5$ тас бес тастан тұратын үздіксіз сызық құрайтындай орналасса (көлденең, тік немесе көлденең сызыққа $45^\circ/135^\circ$ бұрыштағы диагональ бойынша), бұл қатарынан бес тас жиынтығы деп аталады. Бір тарап қатарынан бес тас жиынтығын алған кезде ойын аяқталмайды.
• Ойын алдын ала белгіленген жүрістер санына жеткенде аяқталады.

Сіздің міндетіңіз — берілген тізбектегі $n$ жүрістің әрқайсысынан кейін жаңа ғана өз тасын қойған ойыншының қатарынан бес тас жиынтықтарының жалпы санын шығару.

Кіріс деректер

Бір тест файлында бірнеше тест жиынтығы бар. Кірістің бірінші жолында тесттер санын білдіретін бір бүтін $T$ ($1 \le T \le 10^4$) саны берілген.

Әрбір тест үшін:

• Бірінші жолда жүрістер санын білдіретін бүтін $n$ ($1 \le n \le 10^4$) саны берілген.
• Келесі $n$ жолдың әрқайсысында $i$-ші жүрістің координаталарын білдіретін екі бүтін $x_i, y_i$ ($1 \le x_i, y_i \le 1000$) сандары берілген; бір деректер жиынтығындағы барлық координаталар бірегей екеніне кепілдік беріледі.

Барлық тесттер бойынша $n$ сандарының жалпы қосындысы $10^4$-нен аспайтынына, яғни $\sum n \le 10^4$ екеніне кепілдік беріледі.

Шығыс деректер

Әрбір тест үшін $n$ саннан тұратын бір жолды шығарыңыз, мұндағы $i$-ші сан $i$-ші жүрістен кейін жаңа ғана тасын қойған ойыншының қатарынан бес тас жиынтықтарының жалпы санын көрсетеді.

Мысал

1-мысал

1
14
1 1
2 1
1 2
2 3
1 3
2 5
1 4
2 7
1 5
2 4
1 6
2 2
1 7
2 6

0 0 0 0 0 0 0 0 1 0 2 1 3 3