#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }


const int INF = 1<<29;
struct tup {
    int a, b, c;
    tup(int a, int b, int c) : a(a), b(b), c(c) {}
};

int solve(int N) {
    int offset = 0;
    int a, b, end;
    cin >> a >> b; --a, --b;
    vector<vector<int>> A;
    for (int i = 0; i < N-1; ++i) {
        vector<int> v(3);
        for (int j = 0; j < 3; ++j) cin >> v[j], --v[j];
        sort(v.begin(), v.end());
        if (v[0] == v.back()) ++offset;
        else A.push_back(v);
    }
    cin >> end; --end;
    vector<vector<int>> dp(N, vector<int>(N, -INF));
    dp[a][b] = dp[b][a] = 0;
    int ma = 0;
    vector<int> vma(N, -INF);
    vma[a] = vma[b] = 0;

    for (auto v : A) {
        vector<tup> chs;

        // 3 つのうち 2 つが一緒のとき
        if (v[0] == v[1]) {
            for (int p = 0; p < N; ++p) {
                chs.emplace_back(p, v[2], dp[p][v[1]] + 1);
            }
        }
        else if (v[1] == v[2]) {
            for (int p = 0; p < N; ++p) {
                chs.emplace_back(p, v[0], dp[p][v[1]] + 1);
            }
        }
        // 前の 2 個が一緒
        {
            chs.emplace_back(v[1], v[2], dp[v[0]][v[0]] + 1);
            chs.emplace_back(v[2], v[0], dp[v[1]][v[1]] + 1);
            chs.emplace_back(v[0], v[1], dp[v[2]][v[2]] + 1);
        }
        // 前の 2 個を共に捨てる
        for (int i = 0; i < 3; ++i) {
            for (int j = i+1; j < 3; ++j) {
                chs.emplace_back(v[i], v[j], ma);
            }
        }
        // 前のうち 1 個を捨てる
        for (int i = 0; i < 3; ++i) {
            for (int p = 0; p < N; ++p) {
                chs.emplace_back(p, v[i], vma[p]);
            }
        }

        // change
        for (auto ch : chs) {
            int a = ch.a, b = ch.b, val = ch.c;
            chmax(dp[a][b], val);
            chmax(dp[b][a], val);
            chmax(ma, val);
            chmax(vma[a], val);
            chmax(vma[b], val);
        }
    }
    int res = 0;
    for (int a = 0; a < N; ++a) {
        for (int b = 0; b < N; ++b) {
            if (a == end && b == end) chmax(res, dp[a][b] + 1);
            else chmax(res, dp[a][b]);
        }
    }
    return res + offset;
}

int main() {
    int N;
    while (cin >> N) cout << solve(N) << endl;
}
### Prompt

Develop a solution in CPP to the problem described below:

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 <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }


const int INF = 1<<29;
struct tup {
    int a, b, c;
    tup(int a, int b, int c) : a(a), b(b), c(c) {}
};

int solve(int N) {
    int offset = 0;
    int a, b, end;
    cin >> a >> b; --a, --b;
    vector<vector<int>> A;
    for (int i = 0; i < N-1; ++i) {
        vector<int> v(3);
        for (int j = 0; j < 3; ++j) cin >> v[j], --v[j];
        sort(v.begin(), v.end());
        if (v[0] == v.back()) ++offset;
        else A.push_back(v);
    }
    cin >> end; --end;
    vector<vector<int>> dp(N, vector<int>(N, -INF));
    dp[a][b] = dp[b][a] = 0;
    int ma = 0;
    vector<int> vma(N, -INF);
    vma[a] = vma[b] = 0;

    for (auto v : A) {
        vector<tup> chs;

        // 3 つのうち 2 つが一緒のとき
        if (v[0] == v[1]) {
            for (int p = 0; p < N; ++p) {
                chs.emplace_back(p, v[2], dp[p][v[1]] + 1);
            }
        }
        else if (v[1] == v[2]) {
            for (int p = 0; p < N; ++p) {
                chs.emplace_back(p, v[0], dp[p][v[1]] + 1);
            }
        }
        // 前の 2 個が一緒
        {
            chs.emplace_back(v[1], v[2], dp[v[0]][v[0]] + 1);
            chs.emplace_back(v[2], v[0], dp[v[1]][v[1]] + 1);
            chs.emplace_back(v[0], v[1], dp[v[2]][v[2]] + 1);
        }
        // 前の 2 個を共に捨てる
        for (int i = 0; i < 3; ++i) {
            for (int j = i+1; j < 3; ++j) {
                chs.emplace_back(v[i], v[j], ma);
            }
        }
        // 前のうち 1 個を捨てる
        for (int i = 0; i < 3; ++i) {
            for (int p = 0; p < N; ++p) {
                chs.emplace_back(p, v[i], vma[p]);
            }
        }

        // change
        for (auto ch : chs) {
            int a = ch.a, b = ch.b, val = ch.c;
            chmax(dp[a][b], val);
            chmax(dp[b][a], val);
            chmax(ma, val);
            chmax(vma[a], val);
            chmax(vma[b], val);
        }
    }
    int res = 0;
    for (int a = 0; a < N; ++a) {
        for (int b = 0; b < N; ++b) {
            if (a == end && b == end) chmax(res, dp[a][b] + 1);
            else chmax(res, dp[a][b]);
        }
    }
    return res + offset;
}

int main() {
    int N;
    while (cin >> N) cout << solve(N) << endl;
}
```