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 <bits/stdc++.h>
using namespace std;
int n, a[10000], dp[2010][2010], margin = 1e8, allmax = 1e8, rowmax[2010];
void chmax(int &a, int b) { a = max(a, b); }
int main() {
    cin >> n;
    for(int i = 0; i < 3 * n; ++i) cin >> a[i];
    dp[a[0]][a[1]] = rowmax[a[0]] = rowmax[a[1]] = margin;
    vector<tuple<int, int, int>> update;
    auto upd = [&](int i, int j, int k) {
        for(int _ = 0; _ < 2; _++) {
            update.emplace_back(i, j, k);
            swap(i, j);
        }
    };
    for(int i = 2; i < 3 * n; i += 3) {
        if(a[i] == a[i + 1] and a[i] == a[i + 2]) {
            margin--;
            continue;
        }
        for(int _ = 0; _ < 3; _++) {
            swap(a[i], a[i + 1]), swap(a[i + 1], a[i + 2]);
            upd(a[i], a[i + 1], max(allmax, dp[a[i + 2]][a[i + 2]] + 1));
            for(int j = 1; j <= n; ++j) {
                if(a[i + 1] == a[i + 2]) upd(j, a[i], dp[j][a[i + 1]] + 1);
                upd(j, a[i], rowmax[j]);
            }
        }
        for(auto [e, f, g] : update) chmax(dp[e][f], g), chmax(rowmax[e], g), chmax(allmax, g);
        update.clear();
    }
    cout << allmax - margin << endl;
}