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,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0
#define equals(a,b) (fabs((a)-(b)) < EPS)
 
using namespace std;
 
const int IINF = INT_MAX;
 
// template - begin
class Point{
public:
  double x,y;
 
  Point(double x = 0,double y = 0): x(x),y(y){}
 
  Point operator + (Point p){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}
  Point operator * (Point a){ return Point(x * a.x - y * a.y, x * a.y + y * a.x); }
 
  bool operator < (const Point& p) const{ return !equals(x,p.x)?x<p.x:(!equals(y,p.y)&&y<p.y); }
 
  bool operator == (const Point& p)const{ return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS; }
 
};
 
struct Segment{
  Point p1,p2;
  Segment(Point p1 = Point(),Point p2 = Point()):p1(p1),p2(p2){}
 bool operator == (const Segment& p) const { return ( p.p1 == p1 && p.p2 == p2 ) || ( p.p1 == p2 && p.p2 == p1 ); }
  bool operator < (const Segment& s) const { return !(p1==s.p1)? p1 < s.p1 : p2 < s.p2; }
};
 
typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;
 
ostream& operator << (ostream& os,const Point& a){ os << "(" << a.x << "," << a.y << ")"; }
 
ostream& operator << (ostream& os,const Segment& a){ os << "( " << a.p1 << " , " << a.p2 << " )"; }
 
double dot(Point a,Point b){ return a.x*b.x + a.y*b.y; }
 
double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }
 
double norm(Point a){ return a.x*a.x+a.y*a.y; }
 
double abs(Point a){ return sqrt(norm(a)); }
 
//rad は角度をラジアンで持たせること
Point rotate(Point a,double rad){ return Point(cos(rad)*a.x - sin(rad)*a.y,sin(rad)*a.x + cos(rad)*a.y); }
 
// 度をラジアンに変換
double toRad(double agl){ return agl*M_PI/180.0; }
 
// a => prev, b => cur, c=> next
// prev から cur へ行って next へ行く際の角度を求める
double getArg(Point a,Point b,Point c){
  double arg1 = atan2(b.y-a.y,b.x-a.x);
  double arg2 = atan2(c.y-b.y,c.x-b.x);
  double arg = fabs( arg1 - arg2 );
  while( arg > M_PI ) arg -= 2.0 * M_PI;
  return fabs(arg);
}
// template - end
 
// ccw - begin
int ccw(Point p0,Point p1,Point p2){
  Point a = p1-p0;
  Point b = p2-p0;
  if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
  if(cross(a,b) < -EPS)return CLOCKWISE;
  if(dot(a,b) < -EPS)return ONLINE_BACK;
  if(norm(a) < norm(b))return ONLINE_FRONT;
  return ON_SEGMENT;
}
// ccw - end
 
// intersect - begin
bool intersectLL(Line l, Line m) {
  return abs(cross(l.p2-l.p1, m.p2-m.p1)) > EPS || // non-parallel
         abs(cross(l.p2-l.p1, m.p1-l.p1)) < EPS;   // same line
}
bool intersectLS(Line l, Line s) {
  return cross(l.p2-l.p1, s.p1-l.p1)*       // s[0] is left of l
         cross(l.p2-l.p1, s.p2-l.p1) < EPS; // s[1] is right of l
}
bool intersectLP(Line l,Point p) {
  return abs(cross(l.p2-p, l.p1-p)) < EPS;
}
bool intersectSS(Line s, Line t) {
  return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2) <= 0 &&
         ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2) <= 0;
}
bool intersectSP(Line s, Point p) {
  return abs(s.p1-p)+abs(s.p2-p)-abs(s.p2-s.p1) < EPS; // triangle inequality
}
 
Point projection(Line l,Point p) {
  double t = dot(p-l.p1, l.p1-l.p2) / norm(l.p1-l.p2);
  return l.p1 + (l.p1-l.p2)*t;
}
Point reflection(Line l,Point p) {
  return p + (projection(l, p) - p) * 2;
}
double distanceLP(Line l, Point p) {
  return abs(p - projection(l, p));
}
double distanceLL(Line l, Line m) {
  return intersectLL(l, m) ? 0 : distanceLP(l, m.p1);
}
 
double distanceLS(Line l, Line s) {
  if (intersectLS(l, s)) return 0;
  return min(distanceLP(l, s.p1), distanceLP(l, s.p2));
}
double distanceSP(Line s, Point p) {
  Point r = projection(s, p);
  if (intersectSP(s, r)) return abs(r - p);
  return min(abs(s.p1 - p), abs(s.p2 - p));
}
 
double distanceSS(Line s, Line t) {
  if (intersectSS(s, t)) return 0;
  return min(min(distanceSP(s, t.p1), distanceSP(s, t.p2)),
             min(distanceSP(t, s.p1), distanceSP(t, s.p2)));
}
 
Point crosspoint(Line l,Line m){
  double A = cross(l.p2-l.p1,m.p2-m.p1);
  double B = cross(l.p2-l.p1,l.p2-m.p1);
  if(abs(A) < EPS && abs(B) < EPS){
    vector<Point> vec;
    vec.push_back(l.p1),vec.push_back(l.p2),vec.push_back(m.p1),vec.push_back(m.p2);
    sort(vec.begin(),vec.end());
    assert(vec[1] == vec[2]); //同じセグメントかもよ
    return vec[1];
    //return m.p1;
  }
  if(abs(A) < EPS)assert(false);
  return m.p1 + (m.p2-m.p1)*(B/A);
}
 
// intersect - end
 
// inPolygonP - begin
//cross product of pq and pr
double cross3p(Point p,Point q,Point r)
{
  return (r.x-q.x) * (p.y -q.y) - (r.y - q.y) * (p.x - q.x);
}
   
//returns true if point r is on the same line as the line pq
bool collinear(Point p,Point q,Point r)
{
  return fabs(cross3p(p,q,r)) < EPS;
}
   
//returns true if point t is on the left side of line pq
bool ccwtest(Point p,Point q,Point r)
{
  return cross3p(p,q,r) > 0;//can be modified to accept collinear points
}
  
bool onSegment(Point p,Point q,Point r)
{
  return collinear(p,q,r) && equals(sqrt(pow(p.x-r.x,2)+pow(p.y-r.y,2)) + sqrt(pow(r.x-q.x,2) + pow(r.y-q.y,2) ),sqrt(pow(p.x-q.x,2)+pow(p.y-q.y,2)) ) ;
}
   
 
bool isConvex(vector<Point> p)
{
  int sz = (int)p.size();
   
  if(sz < 3)return false;//boundary case, we treat a point or a line as not convex
   
  bool isLeft = ccwtest(p[0],p[1],p[2]);
   
  for(int i=1; i<(int)p.size();i++)
    if(ccwtest(p[i],p[(i+1)%sz],p[(i+2)%sz]) != isLeft)
      return false;
   
  return true;
}
 
 
double angle(Point a,Point b,Point c)
{
  double ux = b.x - a.x, uy = b.y - a.y;
  double vx = c.x - a.x, vy = c.y - a.y;
  return acos((ux*vx + uy*vy)/sqrt((ux*ux + uy*uy) * (vx*vx + vy*vy)));
}  
   
//多角形poly内（線分上も含む）に点pが存在するかどうは判定する  
bool inPolygon(Polygon poly,Point p)
{
  if((int)poly.size() == 0)return false;
  rep(i,poly.size())
    if(onSegment(poly[i],poly[(i+1)%poly.size()],p))return true;
  double sum = 0;
  for(int i=0; i < (int)poly.size() ;i++)
    {
      if( equals(cross(poly[i]-p,poly[(i+1)%poly.size()]-p),0.0) ) continue; // ３点が平行だとangleがnanを返しsumがnanになり死ぬ
      if(cross3p(p,poly[i],poly[(i+1)%poly.size()]) < 0)
        sum -= angle(p,poly[i],poly[(i+1)%poly.size()]);
      else
        sum += angle(p,poly[i],poly[(i+1)%poly.size()]);
    }
  // あまり誤差を厳しくしすぎると良くないので以下のほうが良い 
  const double eps = 1e-5;
  return (fabs(sum - 2*M_PI) < eps || fabs(sum + 2*M_PI) < eps);
}  
// inPolygonP - end
 
// inPolygonS - begin
bool inPolygon(const Polygon &poly,Segment seg){
  vector<Point> vp;
  vp.push_back(seg.p1);
  vp.push_back(seg.p2);
  rep(i,(int)poly.size()) {
    Segment edge = Segment(poly[i],poly[(i+1)%(int)poly.size()]);
    if( equals(cross(seg.p1-seg.p2,edge.p1-edge.p2),0.0) ) {
      if( onSegment(seg.p1,seg.p2,edge.p1) ) vp.push_back(edge.p1);
      if( onSegment(seg.p1,seg.p2,edge.p2) ) vp.push_back(edge.p2);
    } else {
      if( intersectSS(seg,edge) ) vp.push_back(crosspoint(seg,edge));
    }
  }
  sort(vp.begin(),vp.end());
  vp.erase(unique(vp.begin(),vp.end()),vp.end());
  rep(i,(int)vp.size()-1) {
    Point middle_point = ( vp[i] + vp[i+1] ) / 2.0;
    if( !inPolygon(poly,middle_point) ) return false;
  }
  return true;  
}
// inPolygonS - end
 
const int MAX_V = 16 * 20+2000;
int n,bc[1<<16];
Point ps[16];
Polygon poly;
vector<Segment> segs;
 
bool check(int bitmask){
  int V = segs.size();
  assert( V < MAX_V );
  vector<Point> sp;
  rep(i,n) if( (bitmask>>i) & 1 ) sp.push_back(ps[i]);
  rep(i,V){
    Point mp = ( segs[i].p1 + segs[i].p2 ) / 2.0;
    bool ok = false;
    rep(j,bc[bitmask]){
      Segment seg = Segment(sp[j],mp);
      Point middle = ( seg.p1 + seg.p2 ) / 2.0;
      if( !inPolygon(poly,middle) ) continue;
      //if( !inPolygon(poly,seg) ) continue;
      bool failed = false;
      rep(k,n) {
        if( equals(cross(seg.p1-seg.p2,poly[k]-poly[(k+1)%n]),0.0) ) continue;
        if( intersectSS(seg,Segment(poly[k],poly[(k+1)%n])) ){
          if( onSegment(poly[k],poly[(k+1)%n],seg.p1) || onSegment(poly[k],poly[(k+1)%n],seg.p2) ) continue;
          if( onSegment(seg.p1,seg.p2,poly[k]) || onSegment(seg.p1,seg.p2,poly[(k+1)%n]) ) continue;
          failed = true;
          break;
        } 
      }
      if( !failed ) { ok = true; break; }
    }
    if( !ok ) return false;
  }

  return true;
}
 
Point vir;
bool comp(const Point& p1,const Point& p2){ return !equals(abs(vir-p1),abs(vir-p2)) && abs(vir-p1) < abs(vir-p2); }
 
vector<Segment> makeGraph(){
  vector<Segment> vs;
  rep(i,n) vs.push_back(Segment(ps[i],ps[(i+1)%n]));
  vector<Segment> ret;
  rep(i,vs.size()){
    vector<Point> vp;
    vp.push_back(vs[i].p1);
    vp.push_back(vs[i].p2);
    rep(j,n) REP(k,j+1,n) {
      Segment seg = Segment(ps[j],ps[k]);
      if( equals(cross(vs[i].p1-vs[i].p2,seg.p1-seg.p2),0.0) ) {
        if( onSegment(vs[i].p1,vs[i].p2,seg.p1) ) vp.push_back(seg.p1);
        if( onSegment(vs[i].p1,vs[i].p2,seg.p2) ) vp.push_back(seg.p2);
      } else if( intersectLS(seg,vs[i]) ) vp.push_back(crosspoint(vs[i],seg));
    }
    vir = vs[i].p1;
    sort(vp.begin(),vp.end(),comp);
    vp.erase(unique(vp.begin(),vp.end()),vp.end());
    rep(j,(int)vp.size()-1) ret.push_back(Segment(vp[j],vp[j+1]));
  }
  return ret;
}
 
int main(){
  rep(i,1<<16) bc[i] = __builtin_popcount(i);
  while( cin >> n, n ){
    rep(i,n) cin >> ps[i].x >> ps[i].y;
    poly.resize(n);
    rep(i,n) poly[i] = ps[i]; 
    segs = makeGraph();
    //rep(i,segs.size()) cout << segs[i] << endl;
    //cout << check (552) << endl;
    //return 0;
    int ans = n;
    rep(i,(1<<n)) {
      if( bc[i] >= ans ) continue;
      if( check(i) ) ans = bc[i];
    }
    cout << ans << endl;
  }
  return 0;
}