Coprime Components

Consider an undirected graph $G$ with $N$ vertices, numbered $1$ through $N$. You are given an integer sequence $A_1, A_2, \dots, A_N$ describing the edges of this graph — for each pair of vertices $u$ and $v$, there is an edge between those vertices if and only if $A_u$ and $A_v$ are coprime. Find the number of connected components of $G$. ### Input - The first line of the input contains a sing