Bitwise swaps

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Given a sequence $$a$$ consisting of $$n$$ integers $$a_1,a_2,…,a_n$$, check if you can make this sequence sorted using the following operation :

Pick a pair of indices $$(i,j)$$ with $$i \neq j$$ and $$a_i \& a_j \neq 0$$ then swap the values of $$a_i$$ and $$a_j$$ ($$\&$$ is bitwise and).

Input Specification

The first line contains the number of test cases $$t$$ $$(1\leq t \leq 10^4)$$. Description of the test cases follows. The first line of each test case contains a single integer $$n$$ $$(1\leq n \leq 3.10^5)$$ The second line of each test case contains n integers $$a_1,a_2,…,a_n$$ $$(0 \leq a_i \leq 2^{31}-1)$$

Output Specification

For each test case, print Yes if you can sort the array using the operations described in the statement and No otherwise (case sensitive).

Sample Input

4
3
6 4 2
6
9 34 4 24 1 6
6
9 34 24 4 1 6
2
1 0

Sample Output

Yes
Yes
No
No

Scoring

\begin{array}{|c|c|c|} \hline \text{Group} & \text{Points} & \text{Constraints} \cr \hline 1 & 10 & 0 \leq a_i \leq 1 \cr \hline 2 & 25 & 0 \leq n \leq 3000 \cr \hline 3 & 55 & \text{ No additional constraints } \cr \hline \end{array}