#P5440. [2018年福建冬令营]老虎机

    ID: 4452 传统题 1000ms 256MiB 尝试: 96 已通过: 19 难度: 9 上传者: 标签>CF2700省选/NOI-零和博弈鸽巢原理保留最优候选稀疏状态重置

[2018年福建冬令营]老虎机

Description

有n台老虎机,第i台老虎机里有Li个球,其中第j个球的颜色为Cij。

每次可以选择一台还有球的老虎机,投入一个硬币,它会随机掉出一个球。

求出如果采用最优策略,在最坏情况下,需要多少个硬币才能得到两个颜色相同的球。

注意:你可以根据之前的结果来决定之后的操作,有多组数据。

Format

Input

第一行一个整数t表示数据组数。

每组数据第一行一个整数n,

接下来n行每行第一个整数表示Li,接着Li个整数表示Cij。

1≤t≤101\le t\le10,1≤n,Li,Cij≤1051\le n,L_i,C_{ij}\le10^5,1≤∑iLi≤1051\le\sum_i L_i\le10^5。本站每组测试均保证所有机器合计至少有两个颜色相同的球。

Output

每组数据输出一行一个整数表示答案。

Samples

1
7
4 1 2 3 4
1 1
1 2
1 3
1 4
7 4 7 4 4 7 7 4
1 5
2