This is the easy version of the problem. The only difference from the hard version is that in this version all coordinates are even.

There are n fence-posts at distinct coordinates on a plane. It is guaranteed that no three fence posts lie on the same line.

There are an infinite number of cows on the plane, one at every point with integer coordinates.

Gregor is a member of the Illuminati, and wants to build a triangular fence, connecting 3 distinct existing fence posts. A cow strictly inside the fence is said to be enclosed. If there are an odd number of enclosed cows and the area of the fence is an integer, the fence is said to be interesting.

Find the number of interesting fences.

Input

The first line contains the integer n (3 ≤ n ≤ 6000), the number of fence posts which Gregor can choose to form the vertices of a fence.

Each of the next n line contains two integers x and y (0 ≤ x,y ≤ 10^7, x and y are even), where (x,y) is the coordinate of a fence post. All fence posts lie at distinct coordinates. No three fence posts are on the same line.

Output

Print a single integer, the number of interesting fences. Two fences are considered different if they are constructed with a different set of three fence posts.

Examples

Input


3
0 0
2 0
0 4


Output


1


Input


5
0 0
2 16
30 14
4 6
2 10


Output


3

Note

In the first example, there is only 1 fence. That fence is interesting since its area is 4 and there is 1 enclosed cow, marked in red.

<image>

In the second example, there are 3 interesting fences. 

  * (0,0) — (30,14) — (2,10) 
  * (2,16) — (30,14) — (2,10) 
  * (30,14) — (4,6) — (2,10) 
20
200 716
88 526
434 134
996 890
718 220
820 462
614 178
848 208
724 536
124 710
408 228
846 606
222 32
642 180
694 964
438 994
718 524
688 692
126 494
102 116
 4
12 10
6 14
2 6
6 12

650
 2

// This code wrote by chtholly_micromaker(MicroMaker)
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#include <bits/stdc++.h>
#define reg register
#define ALL(x) (x).begin(),(x).end()
#define mem(x,y) memset(x,y,sizeof x)
#define sz(x) (int)(x).size()
#define ln putchar('\n')
#define lsp putchar(32)
#define pb push_back
#define MP std::make_pair
#ifdef _LOCAL_
#define dbg(x) std::cerr<<__func__<<"\tLine:"<<__LINE__<<' '<<#x<<": "<<x<<"\n"
#define dprintf(x...) std::fprintf(stderr,x)
#else
#define dbg(x) 42
#define dprintf(x...) 42
#endif
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,b,a) for(int i=(b);i>=(a);--i)
typedef std::pair<int,int> pii;
template <class t> inline void read(t &s){s=0;
reg int f=1;reg char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c))s=(s<<3)+(s<<1)+(c^48),c=getchar();s*=f;return;}
template<class t,class ...A> inline void read(t &x,A &...a){read(x);read(a...);}
template <class t> inline void write(t x){if(x<0)putchar('-'),x=-x;
static int buf[21],top=0;while(x)buf[++top]=x%10,x/=10;if(!top)buf[++top]=0;
while(top)putchar(buf[top--]^'0');return;}
inline void setIn(std::string s){freopen(s.c_str(),"r",stdin);return;}
inline void setOut(std::string s){freopen(s.c_str(),"w",stdout);return;}
inline void setIO(std::string s=""){setIn(s+".in");setOut(s+".out");return;}
template <class t>inline bool ckmin(t&x,t y){if(x>y){x=y;return 1;}return 0;}
template <class t>inline bool ckmax(t&x,t y){if(x<y){x=y;return 1;}return 0;}
inline int lowbit(int x){return x&(-x);}
const int MaxN=6050;
int x[MaxN],y[MaxN],n;
typedef unsigned long long ull;
struct Bitset
{
	ull a[MaxN>>6];
	inline void set(int x,ull k){a[x>>6]&=~(1uLL<<(x&63)),a[x>>6]|=(k<<(x&63));}
	inline int test(int x)const{return (a[x>>6]>>(x&63))&1;}
}v[MaxN];
inline int ct(const Bitset &a,const Bitset &b,int st)
{
	st>>=6,st>>=3,st<<=3;
	reg int a1=0,a2=0,a3=0,a4=0,a5=0,a6=0,a7=0,a8=0,m=(MaxN>>6)-1;
	ull *ta=(ull*)&a.a,*tb=(ull*)&b.a;
	ta=ta+st,tb=tb+st;
	for(int i=st;i+8<=m;i+=8,ta=ta+8,tb=tb+8)
	{
		a1+=__builtin_popcountll((*(ta+0))^(*(tb+0)));
		a2+=__builtin_popcountll((*(ta+1))^(*(tb+1)));
		a3+=__builtin_popcountll((*(ta+2))^(*(tb+2)));
		a4+=__builtin_popcountll((*(ta+3))^(*(tb+3)));
		a5+=__builtin_popcountll((*(ta+4))^(*(tb+4)));
		a6+=__builtin_popcountll((*(ta+5))^(*(tb+5)));
		a7+=__builtin_popcountll((*(ta+6))^(*(tb+6)));
		a8+=__builtin_popcountll((*(ta+7))^(*(tb+7)));
	}
	switch(m&7)
	{
		case 7:a7+=__builtin_popcountll((*(ta+6))^(*(tb+6)));
		case 6:a6+=__builtin_popcountll((*(ta+5))^(*(tb+5)));
		case 5:a5+=__builtin_popcountll((*(ta+4))^(*(tb+4)));
		case 4:a4+=__builtin_popcountll((*(ta+3))^(*(tb+3)));
		case 3:a3+=__builtin_popcountll((*(ta+2))^(*(tb+2)));
		case 2:a2+=__builtin_popcountll((*(ta+1))^(*(tb+1)));
		case 1:a1+=__builtin_popcountll((*(ta+0))^(*(tb+0)));
	}
	return a1+a2+a3+a4+a5+a6+a7+a8;
}
int vis[MaxN];
signed main(void)
{
//	setIn("data.in");

	read(n);
	for(int i=1;i<=n;++i)read(x[i],y[i]);
	for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)
		v[i].set(j,
			!!((std::__gcd(std::abs(x[i]-x[j]),std::abs(y[i]-y[j])))&3));
	reg long long ans=0;
	for(int i=1;i<=n;++i)
	{
		Bitset Vi=v[i];
		for(int j=i+1;j<=n;++j)
		{
			Vi.set(j,0);
			if(!v[i].test(j))ans+=n-j-ct(Vi,v[j],j);
			else ans+=ct(Vi,v[j],j);
		}
	}
	write(ans),ln;
	dprintf("used %.9lf\n",1.0*clock()/CLOCKS_PER_SEC);
	return 0;
}

/*
 * Check List:
 * 1. Input / Output File (OI)
 * 2. long long 
 * 3. Special Test such as n=1
 * 4. Array Size
 * 5. Memory Limit (OI) int is 4 and longlong is 8
 * 6. Mod (a*b%p*c%p not a*b*c%p  ,  (a-b+p)%p not a-b )
 * 7. Name ( int k; for(int k...))
 * 8. more tests , (T=2 .. more)
 * 9. blank \n after a case
*/




