Little Cyan Fish-те жалпы саны $n$ бүтін саннан тұратын $m$ тізбек бар. $1$-ден $n$-ге дейінгі әрбір бүтін сан барлық тізбектерде жиыны дәл бір рет кездеседі.

Ол осы тізбектерді ұзындығы $n$ болатын $p$ алмастыруына біріктіргісі келеді. Бастапқыда $p$ бос болады. Әр қадамда ол бос емес бір тізбекті таңдап, оның бірінші бүтін санын өшіреді де, осы бүтін санды $p$-ның соңына қосады. Ол мұны барлық тізбектер бос болғанша қайталайды.

Егер бүтін санның мәні оның $p$-дағы орнына тең болса, ол $p$-ның қозғалмайтын нүктесі деп аталады. Орындар $1$-ден $n$-ге дейін нөмірленген.

$p$ ішіндегі қозғалмайтын нүктелердің ең аз мүмкін санын табыңыз.

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

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

Әрбір тест жағдайы үшін бірінші жолда сәйкесінше бүтін сандардың жалпы санын және тізбектердің санын білдіретін екі бүтін сан $n$ және $m$ ($1 \le m \le n \le 10^6$) берілген.

Келесі $m$ жол тізбектерді сипаттайды. Осы жолдардың $i$-шісінде бір бүтін сан $k_i$ ($1 \le k_i \le n$), ал одан кейін ретімен $i$-ші тізбекті сипаттайтын $k_i$ бүтін сан $a_{i,1}, a_{i,2}, \ldots, a_{i,k_i}$ ($1 \le a_{i,j} \le n$) берілген.

Әрбір тест жағдайында барлық тізбектер бойынша $k_i$ қосындысы $n$-ге тең екендігіне және $1$-ден $n$-ге дейінгі әрбір бүтін сан барлық тізбектерде жиыны дәл бір рет кездесетіндігіне кепілдік беріледі.

Барлық тест жағдайлары бойынша $n$ қосындысы $10^6$-нен аспайтындығына және барлық тест жағдайлары бойынша $m$ қосындысы $10^6$-нен аспайтындығына кепілдік беріледі.

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

Әрбір тест жағдайы үшін $p$ ішіндегі қозғалмайтын нүктелердің ең аз мүмкін санын білдіретін бір бүтін саннан тұратын бір жолды шығарыңыз.

Мысалдар

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

4
1 1
1 1
3 2
1 1
2 2 3
3 2
2 1 3
1 2
4 2
3 2 1 3
1 4

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

1
0
1
0

Ескертпе

Мысалдағы бірінші тест жағдайында жалғыз мүмкін алмастыру — $[1]$, оның бір қозғалмайтын нүктесі бар.

Мысалдағы екінші тест жағдайында Little Cyan Fish ешқандай қозғалмайтын нүктесі жоқ $p = [2, 3, 1]$ алмастыруын ала алады.

Мысалдағы үшінші тест жағдайында $p = [1, 3, 2]$ — бір қозғалмайтын нүктесі бар оңтайлы алмастыру.

Мысалдағы төртінші тест жағдайында ол ешқандай қозғалмайтын нүктесі жоқ $p = [2, 4, 1, 3]$ алмастыруын ала алады.