Problem: You are an officer of the Department of Land and Transport in Oykot City. The department has a plan to build a subway network in the city central of Oykot.

In the plan, n subway lines are built, and each line has two or more stations. Because of technical problems, a rail track between two stations should be straight and should not have any slope. To make things worse, no rail track can contact with another rail track, even on a station. In other words, two subways on the same floor cannot have any intersection.

Your job is to calculate the least number of required floors in their plan.



Input

The input consists of multiple datasets. Each dataset is formatted as follows:


N
Line1
Line2
...
LineN


Here, N is a positive integer that indicates the number of subway lines to be built in the plan (N ≤ 22), and Linei is the description of the i-th subway line with the following format:


S
X1 Y1
X2 Y2
...
XS YS


S is a positive integer that indicates the number of stations in the line (S ≤ 30), and (Xi, Yi) indicates the coordinates of the i-th station of the line (-10000 ≤ Xi, Yi ≤ 10000). The rail tracks are going to be built between two consecutive stations in the description. No stations of the same line have the same coordinates.

The input is terminated by a dataset of N = 0, and it should not be processed.

Output

For each dataset, you should output the least number of required floors.

Example

Input

2
2
0 0
10 0
2
0 10
10 10
2
2
0 0
10 10
2
0 10
10 0
3
2
0 0
10 10
2
0 10
10 0
2
1 0
1 10
0


Output

1
2
3

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;

// chmax, chmin
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; }

// debug stream of pair, vector
#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; }


////////////////////////////
// 基本要素 (点, 線分)
////////////////////////////

using DD = double;
const DD INF = 1LL<<60;      // to be set appropriately
const DD EPS = 1e-10;        // to be set appropriately
const DD PI = acos(-1.0);
DD torad(int deg) {return (DD)(deg) * PI / 180;}
DD todeg(DD ang) {return ang * 180 / PI;}

/* Point */
struct Point {
    DD x, y;
    Point(DD x = 0.0, DD y = 0.0) : x(x), y(y) {}
    friend ostream& operator << (ostream &s, const Point &p) {return s << '(' << p.x << ", " << p.y << ')';}
};
inline Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
inline Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
inline Point operator * (const Point &p, DD a) {return Point(p.x * a, p.y * a);}
inline Point operator * (DD a, const Point &p) {return Point(a * p.x, a * p.y);}
inline Point operator * (const Point &p, const Point &q) {return Point(p.x * q.x - p.y * q.y, p.x * q.y + p.y * q.x);}
inline Point operator / (const Point &p, DD a) {return Point(p.x / a, p.y / a);}
inline Point conj(const Point &p) {return Point(p.x, -p.y);}
inline Point rot(const Point &p, DD ang) {return Point(cos(ang) * p.x - sin(ang) * p.y, sin(ang) * p.x + cos(ang) * p.y);}
inline Point rot90(const Point &p) {return Point(-p.y, p.x);}
inline DD cross(const Point &p, const Point &q) {return p.x * q.y - p.y * q.x;}
inline DD dot(const Point &p, const Point &q) {return p.x * q.x + p.y * q.y;}
inline DD norm(const Point &p) {return dot(p, p);}
inline DD abs(const Point &p) {return sqrt(dot(p, p));}
inline DD amp(const Point &p) {DD res = atan2(p.y, p.x); if (res < 0) res += PI*2; return res;}
inline bool eq(const Point &p, const Point &q) {return abs(p - q) < EPS;}
inline bool operator < (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x < q.x : p.y < q.y);}
inline bool operator > (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x > q.x : p.y > q.y);}
inline Point operator / (const Point &p, const Point &q) {return p * conj(q) / norm(q);}

/* Line */
struct Line : vector<Point> {
    Line(Point a = Point(0.0, 0.0), Point b = Point(0.0, 0.0)) {
        this->push_back(a);
        this->push_back(b);
    }
    friend ostream& operator << (ostream &s, const Line &l) {return s << '{' << l[0] << ", " << l[1] << '}';}
};


////////////////////////////
// 円や直線の交差判定, 距離
////////////////////////////

/*
 ccw を用いている
 
 P: point
 L: Line
 S: Segment
 
 distancePL は、「点」と「直線」の距離
 distancePS は、「点」と「線分」の距離
 */

int ccw_for_dis(const Point &a, const Point &b, const Point &c) {
    if (cross(b-a, c-a) > EPS) return 1;
    if (cross(b-a, c-a) < -EPS) return -1;
    if (dot(b-a, c-a) < -EPS) return 2;
    if (norm(b-a) < norm(c-a) - EPS) return -2;
    return 0;
}
Point proj(const Point &p, const Line &l) {
    DD t = dot(p - l[0], l[1] - l[0]) / norm(l[1] - l[0]);
    return l[0] + (l[1] - l[0]) * t;
}
Point refl(const Point &p, const Line &l) {
    return p + (proj(p, l) - p) * 2;
}
bool isinterPL(const Point &p, const Line &l) {
    return (abs(p - proj(p, l)) < EPS);
}
bool isinterPS(const Point &p, const Line &s) {
    return (ccw_for_dis(s[0], s[1], p) == 0);
}
bool isinterLL(const Line &l, const Line &m) {
    return (abs(cross(l[1] - l[0], m[1] - m[0])) > EPS ||
            abs(cross(l[1] - l[0], m[0] - l[0])) < EPS);
}
bool isinterSS(const Line &s, const Line &t) {
    if (eq(s[0], s[1])) return isinterPS(s[0], t);
    if (eq(t[0], t[1])) return isinterPS(t[0], s);
    return (ccw_for_dis(s[0], s[1], t[0]) * ccw_for_dis(s[0], s[1], t[1]) <= 0 &&
            ccw_for_dis(t[0], t[1], s[0]) * ccw_for_dis(t[0], t[1], s[1]) <= 0);
}
DD distancePL(const Point &p, const Line &l) {
    return abs(p - proj(p, l));
}
DD distancePS(const Point &p, const Line &s) {
    Point h = proj(p, s);
    if (isinterPS(h, s)) return abs(p - h);
    return min(abs(p - s[0]), abs(p - s[1]));
}
DD distanceLL(const Line &l, const Line &m) {
    if (isinterLL(l, m)) return 0;
    else return distancePL(m[0], l);
}
DD distanceSS(const Line &s, const Line &t) {
    if (isinterSS(s, t)) return 0;
    else return min(min(distancePS(s[0], t), distancePS(s[1], t)), min(distancePS(t[0], s), distancePS(t[1], s)));
}

// 彩色数
const int MOD = 1000000007;
long long power(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}
int chromatic_number(const vector<vector<int> > &G) {
    int n = (int)G.size();
    vector<int> neighbor(n, 0);
    for (int i = 0; i < n; ++i) {
        int S = (1<<i);
        for (int j = 0; j < n; ++j)
            if (G[i][j])
                S |= (1<<j);
        neighbor[i] = S;
    }
    
    // I[S] := #. of inndepndet subset of S
    vector<int> I(1<<n);
    I[0] = 1;
    for (int S = 1; S < (1<<n); ++S) {
        int v = __builtin_ctz(S);
        I[S] = I[S & ~(1<<v)] + I[S & ~neighbor[v]];
    }
    int low = 0, high = n;
    while (high - low > 1) {
        int mid = (low + high) >> 1;
        
        // g[S] := #. of "k independent sets" which cover S just
        // f[S] := #. of "k independent sets" which consist of subseta of S
        // then
        //   f[S] = sum_{T in S} g(T)
        //   g[S] = sum_{T in S} (-1)^(|S|-|T|)f[T]
        long long g = 0;
        for (int S = 0; S < (1<<n); ++S) {
            if ((n - __builtin_popcount(S)) & 1) g -= power(I[S], mid);
            else g += power(I[S], mid);
            g = (g % MOD + MOD) % MOD;
        }
        if (g != 0) high = mid;
        else low = mid;
    }
    return high;
}

int main() {
    int N;
    while (cin >> N, N) {
        vector<vector<int> > G(N, vector<int>(N, 0));
        vector<vector<Line> > lines(N);
        for (int i = 0; i < N; ++i) {
            int num; cin >> num;
            double x, y; cin >> x >> y;
            for (int j = 1; j < num; ++j) {
                double nx, ny; cin >> nx >> ny;
                Line l(Point(x, y), Point(nx, ny));
                lines[i].push_back(l);
                x = nx, y = ny;
            }
        }
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                bool ok = false;
                for (auto li : lines[i]) {
                    for (auto lj : lines[j]) {
                        if (isinterSS(li, lj)) ok = true;
                    }
                }
                if (ok) G[i][j] = G[j][i] = true;
            }
        }
        cout << chromatic_number(G) << endl;
    }
}