蟲蟲世界（Worm World）謎題是由 Cliff Pickover 最先在 Discover 雜誌提出來的。蟲蟲世界是一個數字方陣。蟲要在那裡生活並不容易，那裡的蟲生來就有嚴重的過敏症。當他們第一次接觸到某一個數字，他們的免疫系統會被極度的刺激。假如他們再次碰到這個數字，他們會過敏休克而死。
一隻蟲能在蟲蟲世界中從任何一個格子爬來爬去，他能夠水平或垂直移動，但是不能對角移動。一隻蟲在不死掉的情況下能移動的最長距離是多少呢？以下的圖是一個例子：
給你一個方陣請你寫一個程式找出一隻蟲最長能移動的距離是多少。
Input
輸入的第一列有一個整數代表以下有多少組測試資料。
每組測試資料的第一列，有一個整數 N（0 < N <= 12），代表這方陣的邊長大小。接下來有N列，每列有N個整數（均介於 0 到 1000 之間）代表方陣中的數字。
第一列與第一組測試資料以及各組測試資料間均有一空白列，請參考Sample Input。
Output
對每一組測試資料輸出一列。輸出一隻蟲在蟲蟲世界中最長能爬的距離是多少。
測試資料間亦請輸出一空白列。
| Sample Input | Sample Output |
2 3 1 2 1 2 3 4 3 2 1 8 6 8 18 15 24 20 2 20 6 2 15 2 17 15 3 7 0 11 18 16 20 15 1 11 6 2 6 13 4 17 20 16 5 12 7 2 3 5 18 23 7 13 3 2 2 11 4 23 16 23 10 2 4 12 5 20 17 12 10 1 13 12 6 20 |
4 20 |