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 <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;

#define ALL(s) (s).begin(),(s).end()
#define EACH(i,s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#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) {s<<"{ ";for(int i=0;i<P.size();++i){if(i>0)s<<", ";s<<P[i];}return s<<" }"<<endl;}
template<class T1, class T2> ostream& operator<<(ostream &s, map<T1,T2> P) {s<<"{ ";for(__typeof__(P.begin()) it=P.begin();it!=P.end();++it){if(it!=P.begin())s<<", ";s<<'<'<<it->first<<"->"<<it->second<<'>';}return s<<" }"<<endl;}



typedef long double DD;

const DD INF = 1LL<<30;
const DD EPS = 1e-8;
const DD PI = acos(-1.0);
DD torad(int deg) {return (DD)(deg) * PI / 180;}
DD todeg(DD ang) {return ang * 180 / PI;}

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 << ')';}
};

Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
Point operator * (const Point &p, DD a) {return Point(p.x * a, p.y * a);}
Point operator * (DD a, const Point &p) {return Point(a * p.x, a * p.y);}
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);}
Point operator / (const Point &p, DD a) {return Point(p.x / a, p.y / a);}
Point conj(const Point &p) {return Point(p.x, -p.y);}
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);}
Point rot90(const Point &p) {return Point(-p.y, p.x);}
DD cross(const Point &p, const Point &q) {return p.x * q.y - p.y * q.x;}
DD dot(const Point &p, const Point &q) {return p.x * q.x + p.y * q.y;}
DD norm(const Point &p) {return dot(p, p);}
DD abs(const Point &p) {return sqrt(dot(p, p));}
DD amp(const Point &p) {DD res = atan2(p.y, p.x); if (res < 0) res += PI*2; return res;}
bool eq(const Point &p, const Point &q) {return abs(p - q) < EPS;}
bool operator < (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x < q.x : p.y < q.y);}
bool operator > (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x > q.x : p.y > q.y);}
Point operator / (const Point &p, const Point &q) {return p * conj(q) / norm(q);}

int ccw(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;
}

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);
    }
};

bool isinterSS(Line s, Line t) {
    return (ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 && 
            ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0);
}

bool isinter(vector<Line> s, vector<Line> t) {
    for (int i = 0; i < s.size(); ++i) {
        for (int j = 0; j < t.size(); ++j) {
            if (isinterSS(s[i], t[j])) return true;
        }
    }
    return false;
}


const int MAX = 25;
int N, S, x, y, x2, y2;
vector<Line> seg[MAX];



vector<vector<int> > graph;


// 130917（verifyなし）
// 高速ゼータ変換
// 集合関数 f : 2^V -> R があって、g(S) = Σ(T⊆S) f(T)を求める、O(n2^n)
// n = |V|、|f| = 1<<n
template<class T> void Zeta(vector<T> &f, int n) {
    for (int i = 0; i < n; ++i) 
        for (int s = 0; s < (1<<n); ++s) 
            if ( !(s & (1<<i)) ) 
                f[s] = f[s] + f[s|(1<<i)];
}

// 高速メビウス変換
// 集合関数 g : 2^V -> R があって、f(S) = Σ(T⊆S) (-1)^(|S|-|T|)g(T)を求める、O(n2^n)
// あるいは、g(S) = Σ(T⊆S) f(T)なる関係があってgが分かっている状況からfを求める 
template<class T> void Mebius(vector<T> &g, int n) {
    for (int i = 0; i < n; ++i) 
        for (int s = 0; s < (1<<n); ++s)
            if ( s & (1<<i) )
                g[s] = g[s] - g[s ^ (1<<i)];
}



long long power(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}
    
int Chromatic(vector<vector<int> > &graph) {
    int n = graph.size();
    vector<int> G(n, 0);
    for (int i = 0; i < n; ++i) {
        G[i] |= (1<<i);
        for (int j = 0; j < n; ++j)
            if (graph[i][j])
                G[i] |= (1<<j);
    }
    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&~G[v]];
    }
    int lo = 0, up = n, med;
    while (up - lo > 1) {
        med = (up + lo) >> 1;
        int g = 0;
        for (int s = 0; s < (1<<n); ++s) {
            if (__builtin_popcount(s) & 1) g -= power(I[s], med);
            else g += power(I[s], med);
        }
        if (g != 0) up = med;
        else lo = med;
    }
    return up;
}


int main() {
    while (cin >> N && N) {
        for (int i = 0; i < N; ++i) {
            seg[i].clear();
            
            cin >> S;
            cin >> x >> y;
            for (int j = 1; j < S; ++j) {
                cin >> x2 >> y2;
                Line l(Point(x, y), Point(x2, y2));
                seg[i].push_back(l);
                x = x2, y = y2;
            }
        }
        
        graph.clear();
        graph.resize(N, vector<int>(N, 0));
        
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (i == j) continue;
                if (isinter(seg[i], seg[j])) graph[i][j] = 1;
            }
        }
        
        //COUT(graph);
        cout << Chromatic(graph) << endl;
    }
    
    return 0;
}