问题 F: 密码

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:21 通过:11

题目描述

染染船长的船触礁了!

幸运的是,旁边就有一座小岛。

不幸的是,小岛岸边有些荒芜。

幸运的是,小岛上发现了宝箱。

不幸的是,打开宝箱需要密码。

幸运的是,在附近发现了说明。

不幸的是,是染染看不懂的字。

经过不断破译,染染终于知道了如何获得宝箱的密码!
宝箱的密码是一个非负整数 x,x 满足 n 条整系数线性方程,第 i 条方程形如 aix+bi=ci。
原本染染只要随便解就一条方程就行了,然而描述方程的语言的模糊性极强,可以理解为对于特定的第 i 条方程,实际上 ai,bi,ci 的顺序是不确定的。或者说,对于第 i 条方程给出了三个参数 ui,vi,wi,但对于实际的方程 aix+bi=ci,系数和参数之间的一一对应不确定:可能是 ai=ui,bi=vi,ci=wi,可能是 ai=vi,bi=wi,ci=uia,也可能是 ai=wi,bi=ui,ci=vi等。
但是,经过观察,水手中的高手发现,仍然可以确定唯一一个 x 作为密码。
染染想要得到宝藏,请解出 x。

输入格式

本题单个测试点内包含多组测试数据。
输入第一行一个正整数 (1≤T≤20),表示数据组数。
每组数据第一行一个正整数 n (1≤n≤105),表示方程数量。
接下来 n 行,第 i 行包含三个整数 ui,vi,wi (−109≤ui,vi,wi≤109,ui≠0,vi≠0,wi≠0),意义如题。
保证单个测试点内每组数据中 n 的和不超过 106

输出格式

对于每组数据输出一行一个非负整数表示答案 x,保证存在且仅存在一个 x

输入样例 复制

3
1
1 3 6
2
3 1 10
14 2 4
1
1 1 1

输出样例 复制

3
3
0