There was a large mansion surrounded by high walls. The owner of the mansion loved cats so much that he always prepared delicious food for the occasional cats. The hungry cats jumped over the high walls and rushed straight to the rice that was everywhere in the mansion.

One day the husband found some cats lying down in the mansion. The cats ran around the mansion in search of food, hitting and falling. The husband decided to devise a place to put the rice in consideration of the safety of the cats.

<image>

Seen from the sky, the fence of this mansion is polygonal. The owner decided to place the rice only at the top of the polygon on the premises so that the cats could easily find it. Also, since cats are capricious, it is unpredictable from which point on the circumference of the polygon they will enter the mansion. Therefore, the husband also decided to arrange the rice so that no matter where the cat entered, he would go straight from that point and reach one of the rice.

You can meet this condition by placing rice at all vertices. However, it is difficult to replenish the rice and go around, so the master wanted to place the rice at as few vertices as possible. Now, how many places does the master need to place the rice?

Enter the polygon that represents the wall of the mansion as an input, and create a program that finds the minimum number of vertices on which rice is placed. However, the cat shall be able to go straight only inside the polygon (the sides shall be included inside the polygon).



input

The input consists of multiple datasets. The end of the input is indicated by a single zero line. Each dataset is given in the following format:


n
x1 y1
x2 y2
...
xn yn


The number of vertices of the polygon n (3 ≤ n ≤ 16) is given in the first line. The following n lines give the coordinates of the vertices of the polygon. Each of the n lines consists of two integers separated by one space. xi (-1000 ≤ xi ≤ 1000) indicates the x coordinate of the i-th vertex, and yi (-1000 ≤ yi ≤ 1000) indicates the y coordinate of the i-th vertex. The vertices of a polygon are given in such an order that they visit adjacent vertices counterclockwise.

The number of datasets does not exceed 20.

output

For each data set, the number of vertices on which rice is placed is output on one line.

Example

Input

8
0 0
3 2
6 2
8 6
6 5
7 7
0 4
3 4
8
0 0
5 3
5 2
4 1
6 1
8 6
6 4
2 4
0


Output

1
2
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;

typedef complex<double> Point;
const double EPS = 1e-8;

int sign(double a){
    if(a > EPS) return +1;
    if(a < -EPS) return -1;
    return 0;
}
double dot(Point a, Point b){
    return real(conj(a) * b);
}
double cross(Point a, Point b){
    return imag(conj(a) * b);
}
int ccw(Point a, Point b, Point c) {
    b -= a; c -= a;
    double len = abs(b) * abs(c); // テゥツ?淌」ツ?陛」ツ?古ヲツーツ療」ツ?ォテ」ツ?ェテ」ツつ凝」ツ?ィテ」ツ?催」ツ?ッ1テ」ツ?ォテ」ツ?凖」ツつ?
    if (cross(b, c) > +len * EPS)   return +1; // テ・ツ渉催ヲツ卍づィツィツ暗・ツ崢榲」ツつ?
    if (cross(b, c) < -len * EPS)   return -1; // テヲツ卍づィツィツ暗・ツ崢榲」ツつ?
    if (dot(b, c) < 0)     return +2; // c--a--b テ」ツ?ョテゥツ??ァツ閉ェテ」ツ?ァテ、ツクツ?ァツ崢エテァツキツ堙、ツクツ?
    if (norm(b) < norm(c)) return -2; // a--b--c テ」ツ?ョテゥツ??ァツ閉ェテ」ツ?ァテ、ツクツ?ァツ崢エテァツキツ堙、ツクツ?
    return 0;                         // テァツつケテ」ツ?古ァツキツ堙・ツ按?bテ、ツクツ甘」ツ?ォテ」ツ?づ」ツつ?
}
struct Line : public vector<Point> {
    Line() {}
    Line(const Point& a, const Point& b) {
        push_back(a); push_back(b);
    }
    Point vector() const {
        return back() - front();
    }
};
typedef vector<Point> Polygon; // テ・ツ渉催ヲツ卍づィツィツ暗・ツ崢榲」ツつ甘」ツつ津、ツサツョテ・ツョツ?
Point crosspointLL(Line l, Line m){
    double A = cross(l.vector(), m.vector());
    double B = cross(l.vector(), l[1] - m[0]);
    if(sign(A) == 0 && sign(B) == 0) return m[0]; // テ、ツコツ古ァツ崢エテァツキツ堙」ツ?古ゥツ?催」ツ?ェテ」ツ?」テ」ツ?ヲテ」ツ??」ツつ?
    if(sign(A) == 0) assert(false); // テァツ崢エテァツキツ堙」ツ?古、ツコツ、テ」ツつ湘」ツつ嘉」ツ?ェテ」ツ??
    return m[0] + m.vector() * B / A;
}
// テ、ツクツ。テァツォツッテ」ツつ津・ツ青ォテ」ツ?セテ」ツ?ェテ」ツ??
bool intersectSP(Line s, Point p) {
    return ccw(s[0], s[1], p) == 0 && abs(s[0] - p) > EPS && abs(s[1] - p) > EPS;
}
bool equalLL(Line l, Line m){
    return sign(cross(l.vector(), m[0] - l[0])) == 0;
}
bool intersectLS(Line l, Line s) {
    // テァツ崢エテァツキツ嗟テ」ツ?ォテ」ツ?、テ」ツ??」ツ?ヲテ」ツ??ァツキツ堙・ツ按?テ」ツ?ョテァツォツッテァツつケテ」ツ?古ァツ閉ーテ」ツ?ェテ」ツつ凝・ツ?エテ」ツ?ォテ」ツ?づ」ツつ?
    return sign(cross(l.vector(), s[0] - l[0]) * cross(l.vector(), s[1] - l[0])) <= 0;
}
bool intersectSS(Line s, Line t) {
    bool f = ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 && ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0;
    if(!f) return false;
    Point cp = crosspointLL(s, t);
    return intersectSP(s, cp) && intersectSP(t, cp);
}

Point curr(const Polygon& P, int x){
    return P[x];
}
Point next(const Polygon& P, int x){
    return P[(x + 1) % P.size()];
}

enum { OUT, ON, IN };
int contains(const Polygon& P, const Point& p){
    // テァツつケpテ」ツ?凝」ツつ嘉・ツ債甘ァツ崢エテァツキツ堙」ツつ津」ツ?イテ」ツ?催」ツ??ィツセツコテ」ツ?ィテ、ツコツ、テ・ツキツョテ」ツ?凖」ツつ凝・ツ崢榲ヲツ閉ーテ」ツつ津ヲツ閉ーテ」ツ?暗」ツつ?
    bool in = false;
    for(int i = 0; i < P.size(); i++){
        Point a = curr(P, i) - p;
        Point b = next(P, i) - p;
        if(a.imag() > b.imag()) swap(a, b);
        // aテ」ツ?凝」ツつ叡テ」ツ?ョテァツ崢エテァツキツ堙」ツ?軽=0テ」ツ?ィテ、ツコツ、テ」ツつ湘」ツつ甘」ツ??」ツ?敕」ツ?ョテ、ツコツ、テァツつケテ」ツ?ッテ・ツ篠淌ァツつケテ」ツ?ョテ・ツ渉ウテ・ツ?エテ」ツ?ァテ」ツ?づ」ツつ?
        if(a.imag() <= 0 && 0 < b.imag() && cross(a, b) < 0){ 
            in = !in;
        }
        if(sign(cross(a, b)) == 0 && sign(dot(a, b)) <= 0) return ON;
    }
    return in ? IN : OUT;
}

bool arrivable(Point bp, Point tp, const vector<Line>& poly_line, const Polygon& P){
    if(contains(P, 0.5 * (bp + tp)) == OUT) return false;

    Line cat(bp, tp);
    for(int k = 0; k < poly_line.size(); k++){
        Line pol = poly_line[k];
        if(equalLL(cat, pol)) continue;
        if(intersectSS(cat, pol)) return false;
    }

    return true;
}

int main(){
    int N;
    while(cin >> N && N){
        Polygon P(N);
        for(int i = 0; i < N; i++){
            double x, y;
            cin >> x >> y;
            P[i] = Point(x, y);
        }

        vector<Line> poly_line(N);
        for(int i = 0; i < N; i++){
            poly_line[i] = Line(P[i], P[(i + 1) % P.size()]);
            //fprintf(stderr, "line(%f, %f, %f, %f);\n",
                    //P[i].real() * 100, P[i].imag() * 100, P[(i + 1) % P.size()].real() * 100, P[(i + 1) % P.size()].imag() * 100);
        }

        vector<Point> cand_point = P; // テ・ツ?凖ィツ」ツ愿ァツつケ
        for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++){
            if(i == j) continue;
            Point bp = P[i], ep = P[j];
            Line cat(bp, ep);

            bool is_cross = false;
            Point cross_p;
            Line cross_l;
            int cross_idx;
            for(int k = 0; k < N; k++){
                Line pol = poly_line[k];

                if(equalLL(cat, pol)) continue;
                if(!intersectLS(cat, pol)) continue;

                Point cp = crosspointLL(cat, pol);

                if(!intersectSP(pol, cp)) continue;

                assert(abs(ccw(cat[0], cat[1], cp)) != 1);
                if(dot(cat.vector(), cp - cat[0]) < 0) continue; // true??
                //if(ccw(cat[0], cat[1], cp) != -2) continue; // true???

                if(!is_cross){
                    is_cross = true;
                    cross_p = cp; cross_l = pol;
                    cross_idx = k;
                }else if(abs(cross_p - cat[0]) > abs(cp - cat[0])){
                    cross_p = cp; cross_l = pol;
                    cross_idx = k;
                }

            }
            if(is_cross){
                //fprintf(stderr, "o : line(p[%d] = (%.0f, %.0f), p[%d] = (%.0f, %.0f)) has intersect\n", i, bp.real(), bp.imag(), j, ep.real(), ep.imag());
                //fprintf(stderr, "    line[%d]((%.0f, %.0f), (%.0f, %.0f)) , cross (%f. %f) \n",
                        //cross_idx, cross_l[0].real(), cross_l[0].imag(), cross_l[1].real(), cross_l[1].imag(), cross_p.real(), cross_p.imag());
                //fprintf(stderr, "circle(%f, %f, 5.0);\n", cross_p.real() * 100, cross_p.imag() * 100);
                cand_point.push_back(cross_p + cross_l.vector() * EPS);
                cand_point.push_back(cross_p - cross_l.vector() * EPS);
            }else{
                //fprintf(stderr, "x : line(p[%d] = (%.0f, %.0f), p[%d] = (%.0f, %.0f)) has no intersect\n", i, bp.real(), bp.imag(), j, ep.real(), ep.imag());
            }
        }

        vector<vector<bool>> is_arrivable(N, vector<bool>(cand_point.size(), false));
        for(int i = 0; i < N; i++)
        for(int j = 0; j < cand_point.size(); j++){
            Point bp = P[i], tp = cand_point[j];
            is_arrivable[i][j] = arrivable(bp, tp, poly_line, P);
            //fprintf(stderr, "%c : p[%d] -> (%f, %f)\n", is_arrivable[i][j] ? 'o' : 'x', i, cand_point[j].real(), cand_point[j].imag());
            if(i == 0 && !is_arrivable[i][j]){
                //fprintf(stderr, "line(%f, %f, %f, %f)\n", bp.real() * 100, bp.imag() * 100, tp.real() * 100, tp.imag() * 100);
            }
        }

        int ans = N;
        for(int s = 1; s < (1 << N); s++){
            int bits = __builtin_popcount(s);
            if(bits >= ans) continue;
            vector<bool> ok(cand_point.size(), false);
            for(int i = 0; i < N; i++) if(s >> i & 1)
                for(int j = 0; j < cand_point.size(); j++)
                    ok[j] = ok[j] || is_arrivable[i][j];

            bool is_answer = true;
            for(int i = 0; i < cand_point.size(); i++) if(!ok[i]){
                is_answer = false;
                break;
            }

            if(is_answer) {
                ans = bits;
            }
        }

        cout << ans << endl;
    }
    return 0;
}