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

Solution (in CPP):

Solution:
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);

    int n;
    cin >> n;
    vector<int> A(3 * n, 0);
    for (int i = 0; i < 3 * n; ++i) {
        cin >> A[i];
        --A[i];
    }

    const int INF = 1 << 20;
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, -INF));
    
    auto update = [&](int i, int j, int v) {
        vector<int> X{i, j, n};
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (i == j && X[i] != n) {
                    continue;
                }
                dp[X[i]][X[j]] = max(dp[X[i]][X[j]], v);
            }
        }
    };

    update(A[0], A[1], 0);

    int base = 0;
    for (int i = 2; i + 3 <= 3 * n; i += 3) {
        vector<int> B{A[i], A[i + 1], A[i + 2]};
        vector<vector<int>> DP{dp[A[i]], dp[A[i + 1]], dp[A[i + 2]]};
        auto dpn = dp[n];

        if (A[i] == A[i + 1] && A[i + 1] == A[i + 2]) {
            ++base;
            for (int i = 0; i <= n; ++i) {
                for (int j = 0; j < 3; ++j) {
                    DP[j][i] -= 1;
                }
                dpn[i] -= 1;
            }
        }

        for (int _ = 0; _ < 3; ++_) {
            {
                //[i, j, a, b, c] - [j, a, b] = [i, c]
                for (int i = 0; i <= n; ++i) {
                    int mx = dpn[i];
                    if (B[0] == B[1]) {
                        mx = max(mx, DP[0][i] + 1);
                    } 
                    update(i, B[2], mx);
                }
            }

            {
                //[i, j, a, b, c] - [i, j, a] = [b, c]
                int mx = dpn[n];
                mx = max(mx, DP[0][B[0]] + 1);
                update(B[1], B[2], mx);
            }
            rotate(B.begin(), B.begin() + 1, B.end());
            rotate(DP.begin(), DP.begin() + 1, DP.end());
        }
    }

    int res = 0;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            int ans = dp[i][j];
            if (i == j && A.back() == i) {
                ++ans;
            }
            res = max(res, ans);
        }
    }

    res += base;

    cout << res << '\n';

    return 0;
}