丁丁共和國

內容 ：


丁丁共和國的國民非常喜歡賽車，每個人從小的夢想就是當個賽車選手，國內共有數百個層級不同的賽車聯盟，每天都有十幾場不同類型的賽事進行著，賽車已經成為丁丁共和國的國民運動，自從2080年賽車列入奧運項目後，丁丁共和國永遠都是靠這個項目奪得每次奧運的唯一一面獎牌。





為了慶祝丁丁共和國建國一百年，丁丁總理決定舉辦一場盛大的賽車活動，他決定在國內的高速公路中挑選出一條最長的路徑來舉辦這場賽車，身為體育部長的你必須幫總理挑出這條路徑。





丁丁共和國內有數千個城市，而城市間有一些高速公路連接，但是由於丁丁交通部長的省錢政策，丁丁共和國的高速公路有一個特性，就是任意兩個城市間由高速公路構成的路徑都不多不少恰好為一條，而且連接兩個城市的高速公路長度都是1。


輸入說明 ：
輸入檔中會有多筆資料，第一行是一個正整數k，代表一共有多少組資料，接下來是k組測試資料，每組測試資料的第一行是一個正整數n，代表城市的數量，n的大小不會超過2000，接下來每行會有兩個城市名稱，代表這兩個城市間有高速公路連接，城市名稱不會超過100個字元且不含空白，當兩個城市名稱為等號時代表一組測試資料結束，不要把最後一行納入處理。


輸出說明 ：
對每組測試資料，輸出一行所能找到的最長賽道長度。


範例輸入 ：


2
3
A B
B C
= =
4
A B
B C
B D
= =


範例輸出 ：


2
2




出處 ：
2007 NPSC 高中組決賽