あなたは最近開店した洋菓子店のオーナーです。
ショーケースの中には $N$ 種類のケーキが一列に並んでおり、それぞれの値段は $a_1, a_2, \cdots, a_N$ です。

数字に強いこだわりを持つお客さんにケーキを買ってもらうため、隣り合う種類の値段の最大公約数を $1$ より大きくしたいと考えました。
そのためにショーケースに新しい種類のケーキを $0$ 個以上追加したいと思います。

追加するケーキの種類の最小個数を答えてください。
もし、そのような方法がなければ $-1$ を出力してください。

また、この問題はマルチテストケースです。$ T $ 個のテストケースについて答えてください。

・ $ 2 \leq N \leq 2 \times 10^4 $
・ $ 1 \leq a_i \leq 10^ 9 $
・ $ 1 \leq T \leq 10 $
・ 入力はすべて整数です。

入力は標準入力から与えられます。入力の $1$ 行目は以下の通りです。

$ T $

そして、続く $ 2 T$ 行が $T$ 個のテストケースを表します。
これらはそれぞれ以下の形式の行です。

$ N $
$ a_1 \ a_2\  \dots \ a_N $

各テストケースに対し、答えを標準出力に出力してください。
なお、テストケースごとに改行をしてください。