Consider a sequence A1,A2,…,AN$A_1,A_2,\dots ,A_N$, where initially, Ai=i$A_i=i$ for each valid i$i$. You may perform any number of operations on this sequence (including zero). In one operation, you should choose two valid indices i$i$ and j$j$, compute the greatest common divisor of Ai$A_i$ and Aj$A_j$ (let's denote it by g$g$), and change both Ai$A_i$ and Aj$A_j$ to g$g$.

You are given a sequence B1,B2,…,BN