The Tengo-lengo-tengo Football Federation (FFT) is organizing the Tengo-lengo-tengo World Cup, a tournament unlike anything ever seen before. For the opening show, the organizers placed a line of $$$N$$$ flags on the field. The $$$i$$$-th flag represents one of the teams in the cup and has an integer $$$A_i$$$ written on it.

During the show, flags will be removed from the field through arretada removals. A removal is called arretada when the opening crew chooses a non-empty segment of consecutive flags, say from position $$$L$$$ to position $$$R$$$, such that: $$$$$$\gcd(A_L, A_{L+1}, \ldots, A_R) \gt 1 $$$$$$ Here, $$$\gcd$$$ denotes the greatest common divisor of the involved numbers. In an arretada removal, all flags in that segment are removed. After that, the remaining flags close the gap, keeping the same relative order as before.

One possible sequence of removals for the second sample. In each row, the highlighted flags are removed.

To plan the opening show properly, the FFT wants to know the minimum number of arretada removals needed to remove all flags during the presentation.