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;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 2005;
 
int a[N * 3], f[N][N], g[N], gt[N], now, ans;
void update(int x, int y, int t) {
    f[x][y] = max(f[x][y], t);
    now = max(now, t);
    gt[x] = max(gt[x], t);
    gt[y] = max(gt[y], t);
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= 3 * n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) f[i][j] = -INF;
    for (int i = 1; i <= n; i++) gt[i] = -INF;
    update(a[1], a[2], 0);
    for (int j = 1; j <= n; j++) g[j] = gt[j];
    ans = now;
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        int x = a[i * 3], y = a[i * 3 + 1], z = a[i * 3 + 2];
        if (x == y && x == z) {
            cnt++;
            continue;
        }
        if (x == y || x == z || y == z) {
            if (x == z) swap(y, z);
            if (y == z) swap(x, z);
            int t = f[z][z];
            int sb = f[x][z]; // 可能会被改掉
            for (int j = 1; j <= n; j++) {
                update(j, z, max(f[j][x], j == z ? sb : f[x][j]) + 1);
            }
            update(x, y, t + 1);
        } else {
            update(x, y, f[z][z] + 1);
            update(x, z, f[y][y] + 1);
            update(y, z, f[x][x] + 1);
        }
        for (int j = 1; j <= n; j++) {
            update(j, x, g[j]);
            update(j, y, g[j]);
            update(j, z, g[j]);
        }
        update(x, y, ans);
        update(x, z, ans);
        update(y, z, ans);
        for (int j = 1; j <= n; j++) g[j] = gt[j];
        ans = now;
    }
    ans = max(ans, f[a[n * 3]][a[n * 3]] + 1);
    printf("%d\n", ans + cnt);
    return 0;
}