GCD Sort

You are given an array $A$ of length $N$. You are allowed to perform the following operation any number of times (possibly $0$): - Select an index $i \ (1 \leq i \lt N)$ and replace $A_{i+1}$ with $\gcd(A_i, A_{i+1})$. Is it possible to sort $A$ in non-decreasing order after performing the above operation some number of times? ### Input - The first line of input contains a single integer $T$,