在『踢歐埃實業坊』最新推出的一款遊戲中，你所要扮演的，是個不斷在人生中進行是非抉擇的努力人。每一次到達人生的分岔點，都會被詢問一個是非題，例如「今天午餐吃學生餐廳嗎？」。不管選擇的是「是」還是「否」，都會花一分鐘然後抵達下一個人生的分岔點。當然，因為是人生的分岔點，因此做的決定不同，下次遇到的問題也都會不同。對了，第一次面臨人生抉擇不需要耗費任何時間，並且一個結局也需要一分鐘的時間跑動畫。
這款遊戲最厲害的，則是高達五十萬種精彩結局(包含一些隱藏結局)，這對皮皮來說具有莫名的吸引力。因此，皮皮決定將所有的結局都找出來！
不過，可惜的是，這款遊戲僅僅設計了一個存檔空間，也就是說，你只能從最後一次存檔的地方開始玩，或是從頭開始玩。
請你幫皮皮計算，至少要花多少的時間，才能將所有的結局動畫完整地跑過一次呢？
輸入的第一行有一個整數 T (1<=T<=30) 表示有幾組測資。
每筆測試資料的第一行有一個正整數 n (2<=n<=500000)，表示這款遊戲的這個版本總共有 n-1 個抉擇問題(也就是有 n 種精彩結局)。接下來有 n-1 列，第 i 列有兩個數字 Yes[i], No[i]，它們分別表示，針對第 i 個問題你回答「是」和「否」分別會跑到哪一個分岔點，若該數字為 n，則代表它是一個結局。
特別注意的是，對於所有的 i，都滿足 (i+1 <= Yes[i], No[i] <= n)，並且保證不會有兩個人生分岔點走到相同的分岔點。
起點的編號為1。
對於每一筆測試資料，請輸出找出所有結局動畫所需的最少時間。請參考範例測試資料。
第一筆範例測資的解釋：1->Yes(結局) 1(重玩)->No 2(記錄)->No(結局) 2(讀擋)->Yes 3(記錄)->Yes (結局) 3(讀擋)-> No 4(記錄)-> Yes(結局) 4(讀檔)...
Migrated from old NTUJ.
aizu
| No. | Testdata Range | Score |
|---|