import Data.Maybe
import Data.List
import qualified Data.ByteString.Char8 as BS
main=do
 n<-fst.fromJust.BS.readInteger<$>BS.getLine
 a<-map(fst.fromJust.BS.readInteger).BS.words<$>BS.getLine
 print$f (n+1) a [(0,0)] [(0,0)]

f n a [] r=f n a (drop 2$reverse$scanl' (\(_,s) (e,_)->(e,s`gcd`e)) (0,0) r) [(0,0)]

f n [] ((el,sl):l) ((er,sr):r)
 |sl`gcd`sr==1=n+f n [] l ((er,sr):r)
 |otherwise=0

f n (a:as) ((el,sl):l) ((er,sr):r)
 |sl`gcd`sr==1=n+f n (a:as) l ((er,sr):r)
 |otherwise=f (n-1) as ((el,sl):l) ((a,sr`gcd`a):(er,sr):r)