Lucky Şəhərlər#1369
John Rumıniyaya Cənub-Şərqi Avropa Regional yarışmaları üçün təzə gəlib. John əvvəllər Rumıniyada olmayıb, ona görə də yerli sakinlər onun üçün bir ekskursiya təşkil etməyə qərar veriblər. Bu tur bir neçə Rumıniya şəhərini əhatə edəcək və hər şəhərə ən çox bir dəfə baş çəkiləcək. John bir şəhərdə başlayacaq, bələdçili tura uyğun başqa şəhərləri gəzip, və sonra başladığı şəhərə qayıdacaq.
Ölkədə şəhər var, -dən -ə kimi nömrələnib, və ikitərəfli yol var. Hər bir yol iki fərqli şəhəri birləşdirir. John üçün bir ekskursiyanı nəzərdən keçirək: c_1, c_2, \ldots, c_n, burada hər c_i Rumıniyada bir şəhərdir. Bütün c_i-lər fərqli olmalıdır. Hər i = 1, 2, \ldots, n-1 üçün c_i ilə c_{i+1} arasında yol olmalıdır və həmçinin c_n ilə c_1 arasında da yol olmalıdır.
John qeyri-adi insandır və tək sayda şəhər görmək istəyir. Təşkilatçılar tək sayda şəhər ziyarət olunan bütün mümkün turları planlaşdırıblar. Bir şəhər "şanslı" adlanır, əgər ən azı bir tur ondan keçir. Sizin vəzifəniz Rumıniyada neçə şanslı şəhər olduğunu hesablamaqdır.
Birinci sətirdə test tapşırıqlarının sayı verilir. Hər test tapşırığı bir sətirdə iki tam ədəd — və (vergüllə ayrılmış) ilə başlayır. Növbəti sətrin hər birində iki tam ədəd a_i və b_i (vergüllə ayrılmış) verilir, hansı ki -ci yolun birləşdirdiyi şəhərlərin nömrələridir.
Məhdudiyyətlər: 1 \le T \le 77, 0 \le N, M \le 100\,000 (10^5), 1 \le a_i < b_i \le N.
Hər test tapşırığı üçün cavabı ayrıca sətirdə çap edin.
Nümunə 1