問題文

二次元座標平面上で $N$ 体のUMA（未確認動物、Unidentified Mysterious Animal）が暮らしている。 それぞれ $1, 2, \dots, N$ と番号付けたとき、 $i$ 番目のUMAは格子点 $(x_i, y_i)$ に生息しており、そこから動くことはない。

UMAの研究のため、座標平面上から任意にいくつかの点を選んでKMA（桂馬型観察装置、Keima-shaped Monitoring Apparatus）を設置することにした。 KMAは、それぞれ独立に東西南北のいずれかの向きに設置する。 KMAを点 $(a, b)$ に置くと、そのKMA経由で以下の点が観察可能になる。

• 東を向いているとき、 $(a + 2, b - 1)$ と $(a + 2, b + 1)$
• 西を向いているとき、 $(a - 2, b - 1)$ と $(a - 2, b + 1)$
• 南を向いているとき、 $(a - 1, b - 2)$ と $(a + 1, b - 2)$
• 北を向いているとき、 $(a - 1, b + 2)$ と $(a + 1, b + 2)$

一方で、KMAの配置には制約があり、以下の条件を満たす必要がある。

• UMAの生息点にKMAを設置してはいけない。
• 同じ点にKMAを複数設置することはできない。

この条件のもと、適切にKMAを配置することで $N$ 体のUMAの生息点すべてを観察可能にできるだろうか？ またそのとき、最小で何個のKMAが必要だろうか？

制約

• 入力はすべて整数
• $1 \leq N \leq 16$
• $0 \leq x_i \leq 1000$
• $0 \leq y_i \leq 1000$
• $i \neq j$ ならば $(x_i, y_i) \neq (x_j, y_j)$

入力

入力は以下の形式で標準入力から与えられます。

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

出力

適切にKMAを配置することで $N$ 体のUMAの生息点すべてを観察可能にできるとき、必要なKMAの最小個数を一行に出力してください。 そうでないとき、 -1 を出力してください。 最後に改行してください。

サンプル

3
0 3
2 1
2 3

2

9
3 3
5 4
4 5
2 5
1 4
1 2
2 1
4 1
5 2

-1