Problem: Major Mickle is commanded to protect a secret base which is being attacked by N tanks. Mickle has an ultimate laser rifle called Mickle's beam. Any object shot by this beam will be immediately destroyed, and there is no way for protection. Furthermore, the beam keeps going through even after destroying objects. The beam is such a powerful and horrible weapon, but there is one drawback: the beam consumes a huge amount of energy. For this reason, the number of shots should be always minimized.

Your job is to write a program that calculates the minimum number of shots required to destroy all the enemy tanks.

You can assume the following:

* the base is located on the origin (0, 0);
* each tank has a rectangular shape with edges parallel to the x- and y-axes;
* no tank may touch or include the origin;
* no two tanks share the same point;
* the width of beam is negligible; and
* a beam destroys every tank it touches or crosses.



Input

The input consists of an integer sequence.

The first integer indicates N (N ≤ 2,000). Each of the following N lines contains four integers which indicates the x- and y-coordinates of the lower-left corner and the upper-right corner of a tank respectively. You can assume that every coordinate may not exceed 10,000 in absolute value.

Output

Output the minimum number of shots of the beam.

Example

Input




Output

Solution (in CPP):

Solution:
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<list>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<string>
#define sgn(v) (abs((v))<eps?0:((v)<0?-1:1))
#define sqr(v) ((v)*(v))
#define MP make_pair
#define PB push_back
#define FI first
#define SE second
#define debug 0
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<double,int> PDI;
typedef pair<double,double> PDD;
typedef pair<int,int> PII;
typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
typedef pair<LL,LL> PLL;
const double eps=1e-9;
const double pi=acos(-1);
vector<PDD> it,tp;
double ag[4];
bool cmpSE(PDD p,PDD q)
{
	if(sgn(p.SE-q.SE))return p.SE<q.SE;
	else return p.FI<q.FI;
}
bool cmpFI(PDD p,PDD q)
{
	if(sgn(p.FI-q.FI))return p.FI<q.FI;
	else return p.SE<q.SE;
}
bool In(double v,double l,double r)
{
	for(int k=-3;k<=3;++k)
		if((sgn(l-v-k*2*pi)<=0&&sgn(v+k*2*pi-r)<=0))return true;
	return false;
}
int main()
{
	//cout <<pi/4*3<<endl;
	int n,i,j,con;
	int x1,y1,x2,y2;
	double l,r,nr;
	scanf("%d",&n);
	for(i=0;i<n;++i)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		ag[0]=atan2(y1,x1);ag[1]=atan2(y1,x2);
		ag[2]=atan2(y2,x1);ag[3]=atan2(y2,x2);
		sort(ag,ag+4);
		l=ag[0],r=ag[3];
		//cout <<ag[0]<<" "<<ag[1]<<" "<<ag[2]<<" "<<ag[3]<<endl;cout <<l<<" "<<r<<endl;
		if(sgn(r-l-pi)>0)
		{
			for(j=0;j<4;++j)if(sgn(ag[j])<0)ag[j]+=2*pi;
			sort(ag,ag+4);
			l=ag[0],r=ag[3];
		}
		//cout <<l<<" "<<r<<endl;
		if(sgn(l-r)>0)while(1);
		it.PB(MP(l,r));
	}
	sort(it.begin(),it.end());
	//for(i=0;i<it.size();++i)cout <<it[i].FI<<" "<<it[i].SE<<endl;
	int ans=n;
	for(i=0;i<it.size();++i)
	{
		nr=it[i].FI;
		tp.clear();
		con=1;
		for(j=0;j<i;++j)
		{
			if(In(nr,it[j].FI,it[j].SE))continue;
			tp.PB(MP(it[j].FI+2*pi,it[j].SE+2*pi));
		}
		for(j=i+1;j<it.size();++j)
		{
			if(In(nr,it[j].FI,it[j].SE))continue;
			tp.PB(it[j]);
		}
		sort(tp.begin(),tp.end(),cmpSE);
		//cout <<"This is l:"<<nr<<" "<<tp.size()<<endl;for(j=0;j<tp.size();++j)cout <<tp[j].FI<<" "<<tp[j].SE<<endl;
		for(j=0;j<tp.size();++j)
		{
			if(j==0||!(In(nr,tp[j].FI,tp[j].SE)))
				nr=tp[j].SE,++con;
		}
		ans=min(ans,con);
		nr=it[i].FI;
		tp.clear();
		con=1;
		for(j=0;j<i;++j)
		{
			if(In(nr,it[j].FI,it[j].SE))continue;
			tp.PB(MP(it[j].FI+2*pi,it[j].SE+2*pi));
		}
		for(j=i+1;j<it.size();++j)
		{
			if(In(nr,it[j].FI,it[j].SE))continue;
			tp.PB(it[j]);
		}
		sort(tp.begin(),tp.end(),cmpFI);
		//cout <<"This is l:"<<nr<<" "<<tp.size()<<endl;for(j=0;j<tp.size();++j)cout <<tp[j].FI<<" "<<tp[j].SE<<endl;
		for(j=0;j<tp.size();++j)
		{
			if(j==0||!(In(nr,tp[j].FI,tp[j].SE)))
				nr=tp[j].FI,++con;
		}
		ans=min(ans,con);
		//-----------------------------------------------use L-----------------------------------------------------
		nr=it[i].SE;
		tp.clear();
		con=1;
		for(j=0;j<i;++j)
		{
			if(In(nr,it[j].FI,it[j].SE))continue;
			tp.PB(MP(it[j].FI+2*pi,it[j].SE+2*pi));
		}
		for(j=i+1;j<it.size();++j)
		{
			if(In(nr,it[j].FI,it[j].SE))continue;
			tp.PB(it[j]);
		}
		sort(tp.begin(),tp.end(),cmpSE);
		//cout <<"This is r:"<<nr<<" "<<tp.size()<<endl;for(j=0;j<tp.size();++j)cout <<tp[j].FI<<" "<<tp[j].SE<<endl;
		for(j=0;j<tp.size();++j)
		{
			if(j==0||!(In(nr,tp[j].FI,tp[j].SE)))
				nr=tp[j].SE,++con;
		}
		ans=min(ans,con);
		nr=it[i].SE;
		tp.clear();
		con=1;
		for(j=0;j<i;++j)
		{
			if(In(nr,it[j].FI,it[j].SE))continue;
			tp.PB(MP(it[j].FI+2*pi,it[j].SE+2*pi));
		}
		for(j=i+1;j<it.size();++j)
		{
			if(In(nr,it[j].FI,it[j].SE))continue;
			tp.PB(it[j]);
		}
		sort(tp.begin(),tp.end(),cmpFI);
		//cout <<"This is r:"<<nr<<" "<<tp.size()<<endl;for(j=0;j<tp.size();++j)cout <<tp[j].FI<<" "<<tp[j].SE<<endl;
		for(j=0;j<tp.size();++j)
		{
			if(j==0||!(In(nr,tp[j].FI,tp[j].SE)))
				nr=tp[j].FI,++con;
		}
		ans=min(ans,con);
	}
	printf("%d\n",ans);
	return 0;
}