Кішкентай Y саябақты аралап жүр. Бұл саябақтың картасын $n$ төбе мен $m$ қырдан тұратын бағытталмаған қарапайым байланысқан граф түрінде көрсетуге болады. Саяхатшыларға маршруттарын жоспарлауға көмектесу үшін картада бірнеше цикл бар; әрбір циклды өзара әртүрлі $e_1, e_2, \dots, e_l$ төбелер тізбегімен көрсетуге болады, мұндағы $l \ge 3$, және барлық $1 \le i \le l$ үшін графта $e_i$ мен $e_{(i \bmod l)+1}$ төбелерін қосатын қыр бар. Сонымен қатар, циклдағы барлық төбелерді ретімен қосатын қырлар жиыны циклдың қырлар жиыны деп аталады, және екі цикл тек олардың қырлар жиындары әртүрлі болғанда ғана әртүрлі деп есептеледі. Кішкентай Y серуенін жалғастыра отырып, бір қасиетті байқады: графтағы әрбір қыр ең көп дегенде бір циклда ғана кездеседі.

Қазіргі уақытта саябақта жарықтандыру жүйесі жоқ, сондықтан түн түскенде саябақ толығымен қараңғылыққа батады. Бақытымызға орай, қызметкерлер картадағы кейбір төбелерге шамшырақтар орнатуға дайындалып жатыр. Графтағы екі төбенің арасындағы арақашықтық бір төбеден екіншісіне жету үшін жүріп өту керек ең аз қырлар саны ретінде анықталады. Сондықтан әрбір шамшырақ өзі орналасқан төбені жарықтандырумен қатар, сол төбеден арақашықтығы $k$-дан аспайтын барлық төбелерді де жарықтандыра алады.

Спорттық бағдарламалау сайыскері ретінде Кішкентай Y-дің ойына бірден мынадай сұрақ келді: барлық төбелердің жарықтандырылуын қамтамасыз ету үшін кем дегенде қанша шамшырақ орнату қажет?

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

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

Әрбір тест жиыны үшін:

Бірінші жолда картадағы төбелер мен қырлар санын, сондай-ақ шамшырақ жарықтандыра алатын ең үлкен арақашықтықты білдіретін үш бүтін сан $n, m, k$ ($2 \le n \le 2 \times 10^5$, $n-1 \le m \le 2 \times 10^5$, $1 \le k \le n$) берілген.

Келесі $m$ жолдың әрқайсысында картадағы қырды білдіретін екі бүтін сан $u, v$ ($1 \le u, v \le n, u \ne v$) берілген.

Берілген бағытталмаған графтың байланысқан екеніне, еселік қырлары мен ілмектері жоқ екеніне және әрбір қырдың ең көп дегенде бір циклда ғана кездесетініне кепілдік беріледі. Сонымен қатар, барлық тест жиындары бойынша $n$ мен $m$ қосындысы $2 \times 10^5$-нен аспайды.

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

Әрбір тест жиыны үшін орнату қажет шамшырақтардың ең аз санын білдіретін бір бүтін санды шығарыңыз.

Мысал

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

3
5 4 1
1 2
1 3
3 4
1 5
5 5 1
1 2
2 3
3 4
4 5
5 1
8 8 2
1 2
2 3
3 4
4 5
5 1
1 6
2 7
3 8

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

2
2
1

Ескертпе

Бірінші тест жиыны үшін 1-ші және 4-ші төбелерге сәйкесінше екі шамшырақ орнатуға болады.

Екінші тест жиыны үшін 2-ші және 5-ші төбелерге сәйкесінше екі шамшырақ орнатуға болады.

Үшінші тест жиыны үшін мүмкін шешімдердің бірі — 2-ші төбеге бір шамшырақ орнату. Шамшырақтар саны ең аз болу шартын қанағаттандыратын жалғыз шешім осы екенін дәлелдеуге болады.