#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
#define Swap(a,b) (a+=b,b=a-b,a-=b)
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
static inline char GET(void)
{
  static char buf[1<<22],*s1=buf,*s2=buf;
  return s1==s2&&(s2=(s1=buf)+fread(buf,1,1<<22,stdin),s1==s2)?EOF:*s1++;
}
static inline void PUT(char c)
{
  static char buf[1<<15],*ptr=buf;
  if(ptr==buf+strlen(buf)||c==0){fwrite(buf,1,ptr-buf,stdout),ptr=buf;}*ptr++=c;
}
static inline int IN(void)
{
  int x=0,f=0,c=GET();while(c<48||c>57){f^=c==45,c=GET();}
  while(c>47&&c<58){x=x*10+c-48,c=GET();}return f?-x:x;
}
static inline void OUT(int a)
{
  if(a<0)PUT('-'),a=-a;
  int d[40],i=0;do{d[i++]=a%10;}while(a/=10);
  while(i--){PUT(d[i]+48);}PUT('\n');
}
//https://atcoder.jp/contests/abc176/submissions/16571317
//https://atcoder.jp/contests/abc176/submissions/16449316
static inline int Max(int x,int y){return x>y?x:y;}
int work[10006][3],sz=0;
static inline void Add(int x,int y,int v){work[sz][0]=x;work[sz][1]=y;work[sz++][2]=v;}
int main(void)
{
  int N=IN(),A[3*N],dp[N][N],B[N],mx,extra=0;
  rep(i,3*N)A[i]=IN()-1;
  memset(B,-0x3f,sizeof(B));
  memset(dp,-0x3f,sizeof(dp));
  dp[A[0]][A[1]]=dp[A[1]][A[0]]=B[A[0]]=B[A[1]]=mx=0;
  rep(i,N-1)
  {
    if(A[3*i+2]>A[3*i+3])Swap(A[3*i+2],A[3*i+3]);
    if(A[3*i+3]>A[3*i+4])Swap(A[3*i+3],A[3*i+4]);
    if(A[3*i+2]>A[3*i+3])Swap(A[3*i+2],A[3*i+3]);
    int x[3]={A[3*i+2],A[3*i+3],A[3*i+4]};
    if(x[2]==x[0]){extra++;continue;}
    if(x[0]==x[1])rep(j,N)Add(j,x[2],dp[j][x[0]]+1);
    if(x[1]==x[2])rep(j,N)Add(j,x[0],dp[j][x[1]]+1);
    rep(j,3)Add(x[j==0],x[j==2?1:2],dp[x[j]][x[j]]+1);
    rep(j,3)rep(k,j)Add(x[j],x[k],mx);
    rep(j,N)rep(k,3)Add(j,x[k],B[j]);
    rep(j,sz)if(dp[work[j][0]][work[j][1]]<work[j][2])
      dp[work[j][0]][work[j][1]]=dp[work[j][1]][work[j][0]]=work[j][2],
      B[work[j][0]]=Max(B[work[j][0]],work[j][2]),
      B[work[j][1]]=Max(B[work[j][1]],work[j][2]),mx=Max(mx,work[j][2]);
    sz=0;
  }
  return OUT(Max(mx,dp[A[3*N-1]][A[3*N-1]]+1)+extra),0;
}
### Prompt

Please create a solution in cpp to the following problem:

We have 3N cards arranged in a row from left to right, where each card has an integer between 1 and N (inclusive) written on it. The integer written on the i-th card from the left is A_i.

You will do the following operation N-1 times:

* Rearrange the five leftmost cards in any order you like, then remove the three leftmost cards. If the integers written on those three cards are all equal, you gain 1 point.



After these N-1 operations, if the integers written on the remaining three cards are all equal, you will gain 1 additional point.

Find the maximum number of points you can gain.

Constraints

* 1 \leq N \leq 2000
* 1 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 \cdots A_{3N}


Output

Print the maximum number of points you can gain.

Examples

Input

2
1 2 1 2 2 1


Output

2


Input

3
1 1 2 2 3 3 3 2 1


Output

1


Input

3
1 1 2 2 2 3 3 3 1


Output

3

### Response

```cpp
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
#define Swap(a,b) (a+=b,b=a-b,a-=b)
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
static inline char GET(void)
{
  static char buf[1<<22],*s1=buf,*s2=buf;
  return s1==s2&&(s2=(s1=buf)+fread(buf,1,1<<22,stdin),s1==s2)?EOF:*s1++;
}
static inline void PUT(char c)
{
  static char buf[1<<15],*ptr=buf;
  if(ptr==buf+strlen(buf)||c==0){fwrite(buf,1,ptr-buf,stdout),ptr=buf;}*ptr++=c;
}
static inline int IN(void)
{
  int x=0,f=0,c=GET();while(c<48||c>57){f^=c==45,c=GET();}
  while(c>47&&c<58){x=x*10+c-48,c=GET();}return f?-x:x;
}
static inline void OUT(int a)
{
  if(a<0)PUT('-'),a=-a;
  int d[40],i=0;do{d[i++]=a%10;}while(a/=10);
  while(i--){PUT(d[i]+48);}PUT('\n');
}
//https://atcoder.jp/contests/abc176/submissions/16571317
//https://atcoder.jp/contests/abc176/submissions/16449316
static inline int Max(int x,int y){return x>y?x:y;}
int work[10006][3],sz=0;
static inline void Add(int x,int y,int v){work[sz][0]=x;work[sz][1]=y;work[sz++][2]=v;}
int main(void)
{
  int N=IN(),A[3*N],dp[N][N],B[N],mx,extra=0;
  rep(i,3*N)A[i]=IN()-1;
  memset(B,-0x3f,sizeof(B));
  memset(dp,-0x3f,sizeof(dp));
  dp[A[0]][A[1]]=dp[A[1]][A[0]]=B[A[0]]=B[A[1]]=mx=0;
  rep(i,N-1)
  {
    if(A[3*i+2]>A[3*i+3])Swap(A[3*i+2],A[3*i+3]);
    if(A[3*i+3]>A[3*i+4])Swap(A[3*i+3],A[3*i+4]);
    if(A[3*i+2]>A[3*i+3])Swap(A[3*i+2],A[3*i+3]);
    int x[3]={A[3*i+2],A[3*i+3],A[3*i+4]};
    if(x[2]==x[0]){extra++;continue;}
    if(x[0]==x[1])rep(j,N)Add(j,x[2],dp[j][x[0]]+1);
    if(x[1]==x[2])rep(j,N)Add(j,x[0],dp[j][x[1]]+1);
    rep(j,3)Add(x[j==0],x[j==2?1:2],dp[x[j]][x[j]]+1);
    rep(j,3)rep(k,j)Add(x[j],x[k],mx);
    rep(j,N)rep(k,3)Add(j,x[k],B[j]);
    rep(j,sz)if(dp[work[j][0]][work[j][1]]<work[j][2])
      dp[work[j][0]][work[j][1]]=dp[work[j][1]][work[j][0]]=work[j][2],
      B[work[j][0]]=Max(B[work[j][0]],work[j][2]),
      B[work[j][1]]=Max(B[work[j][1]],work[j][2]),mx=Max(mx,work[j][2]);
    sz=0;
  }
  return OUT(Max(mx,dp[A[3*N-1]][A[3*N-1]]+1)+extra),0;
}
```