Content:
简体中文
傳說中,在 NPSC 大陸的某片森林深處住著一群史萊姆。這群史萊姆非常好戰,每當有兩隻史萊姆相遇時,他們總會打 1018 回合,或是打到有其中一方戰死才肯罷休。身為一個史萊姆生態研究員,蚯蚓決定前往這片森林研究這些特別的史萊姆。
在觀察後,蚯蚓發現一個特別的現象:兩隻史萊姆打架時,常常分不出勝負,而且輸贏跟兩隻史萊姆的大小似乎沒什麼關係!在更進一步研究後,蚯蚓發現這似乎與史萊姆特殊的打架方式有關。
假設有兩隻大小為 a, b (a>b) 的史萊姆在打架,則大小為 b (比較小) 的那隻會發動攻擊,並且在攻擊完後將 a 的一部分吸收。這一回合後兩隻史萊姆的大小會變為 a−b, b+b,再由比較小的那隻史萊姆再度發動攻擊,以此類推。若當兩隻史萊姆的大小變得一樣時,兩方會發動最後的攻擊,而速度較快的一方就會擊敗對方、將對方完全吸收,而若在打了 1018 回合後都沒有一方戰敗,兩隻史萊姆就會休戰。
蚯蚓很好奇,在眾多的史萊姆中,究竟有幾對史萊姆相遇時是會分出勝負的?
Input:
輸入檔的第一行有一個正整數 T (T<=10),表示接下來總共有幾筆測試資料。
每一筆測試資料的開頭有一個正整數 N (N<=105),代表森林中有幾隻史萊姆。接下來有 N 個正整數 Si 代表該隻史萊姆的大小,史萊姆的大小不會超過500000。
Output:
Sample Input:
2 3 5 1 4 4 1 2 3 4
Sample Output :
0 1
Hint
:
範例說明:
第二筆測試資料中,只有 (1,3) 能分出勝負。
Author
: