傳說中，在 NPSC 大陸的某片森林深處住著一群史萊姆。這群史萊姆非常好戰，每當有兩隻史萊姆相遇時，他們總會打 10¹⁸ 回合，或是打到有其中一方戰死才肯罷休。身為一個史萊姆生態研究員，蚯蚓決定前往這片森林研究這些特別的史萊姆。

在觀察後，蚯蚓發現一個特別的現象：兩隻史萊姆打架時，常常分不出勝負，而且輸贏跟兩隻史萊姆的大小似乎沒什麼關係！在更進一步研究後，蚯蚓發現這似乎與史萊姆特殊的打架方式有關。

假設有兩隻大小為 a, b (a>b) 的史萊姆在打架，則大小為 b (比較小) 的那隻會發動攻擊，並且在攻擊完後將 a 的一部分吸收。這一回合後兩隻史萊姆的大小會變為 a−b, b+b，再由比較小的那隻史萊姆再度發動攻擊，以此類推。若當兩隻史萊姆的大小變得一樣時，兩方會發動最後的攻擊，而速度較快的一方就會擊敗對方、將對方完全吸收，而若在打了 10¹⁸ 回合後都沒有一方戰敗，兩隻史萊姆就會休戰。

蚯蚓很好奇，在眾多的史萊姆中，究竟有幾對史萊姆相遇時是會分出勝負的？ 

輸入檔的第一行有一個正整數 T (T<=10)，表示接下來總共有幾筆測試資料。

每一筆測試資料的開頭有一個正整數 N (N<=10⁵)，代表森林中有幾隻史萊姆。接下來有 N 個正整數 S_i 代表該隻史萊姆的大小，史萊姆的大小不會超過500000。 

2
3 5 1 4
4 1 2 3 4

0
1

範例說明：

第二筆測試資料中，只有 (1,3) 能分出勝負。