//③将所有的与之相连的边极角排序。
for (int i = 1; i <= n; i++) {
sort(vertex[i].begin(), vertex[i].end());
int ms = vertex[i].size();
//④遍历每条入边。将其后继设为与之顺时针相邻的出边。也就是在G’中连一条从这个入边的点到其后继的有向边。
for (int j = 0; j < ms - 1; j++)
nxt[vertex[i][j].in] = vertex[i][j + 1].out;
nxt[vertex[i][ms - 1].in] = vertex[i][0].out;
}
int ms = m << 1 | 1;
memset(belong, -1, sizeof(belong));
cnt = 0;
//⑤在G'中就是一些不相交的有向环。每个有向环就对应一个区域。找出了所有的区域，我们要的那张图就简单了。
for (int i = 0; i <= ms; i++)
if (belong[i] == -1 && ++cnt > 0)
find(i, i);
//构不成平面的边,会形成一个特殊的区域，相当于进去死胡同再出来。但是答案不会受到影响，所以直接忽略。
}
double work() {
int a, b;
sp.init();
for (int i = 0; i < m; i++) {
a = belong[i << 1];
b = belong[i << 1 | 1];
sp.add(a, b, cap[i]);
sp.add(b, a, cap[i]);
}
a = belong[m << 1];
b = belong[m << 1 | 1];
return sp.solve(a, b);
}
int main() {
int cas;
scanf("%d", &cas);
while (cas--) {
init();
build();
printf("%.0f\n", work());
}
return 0;
}