小藍和小喬正在玩一個游戲：對給定的 n 堆石子，每次可以選一堆石子分成相等的質(zhì)數(shù)份或直接消去。雙方輪流操作，輪到某玩家操作時如果沒有任何石子則這個玩家失敗。

小藍先操作（先手），小喬后操作。

請問小藍是否存在必勝策略，即是不是存在一種策略，使得不論小喬如何操作，小藍總有辦法獲得勝利。

輸入包含多組獨立的詢問。

輸入的第一行包含一個整數(shù) T 表示詢問的組數(shù)。

接下來依次描述每一組詢問。

每組詢問的第一行包含一個整數(shù) n_i ，表示石子的堆數(shù)。

第二行包含 n 個正整數(shù)，相鄰兩個整數(shù)之間用一個空格分隔，依次表示每堆石子的個數(shù)。

輸出 T 行，每行包含一個整數(shù) 0 或 1，表示對應(yīng)詢問的答案。如果小藍存在必勝策略，輸出 1，否則輸出 0 。

2
2
2 3
5
4 15 1 9 6

1
1

對于 20% 的評測用例，T = 1 ，n_i ≤ 10 ，每堆石子數(shù)量不超過 1000；

對于 50% 的評測用例，∑n_i ≤10000；

對于所有評測用例，1 ≤T≤10⁵ ，1≤ n_i ，∑ n_i ≤ 10⁵ ，每堆石子數(shù)量不超過 10⁶ 。