描述

染染船长的船触礁了！

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

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

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

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

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

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

经过不断破译，染染终于知道了如何获得宝箱的密码！

宝箱的密码是一个非负整数 $x$，$x$ 满足 $n$ 条整系数线性方程，第 $i$ 条方程形如 $a_i x + b_i = c_i$。

原本染染只要随便解一条方程就行了，然而描述方程的语言的模糊性极强，可以理解为对于特定的第 $i$ 条方程，实际上 $a_i, b_i, c_i$ 的顺序是不确定的。或者说，对于第 $i$ 条方程给出了三个参数 $u_i, v_i, w_i$，但对于实际的方程 $a_i x + b_i = c_i$，系数和参数之间的一一对应不确定：可能是 $a_i = u_i, b_i = v_i, c_i = w_i$，可能是 $a_i = v_i, b_i = w_i, c_i = u_i$，也可能是 $a_i = w_i, b_i = u_i, c_i = v_i$ 等。

但是，经过观察，水手中的高手发现，仍然可以确定唯一一个 $x$ 作为密码。

染染想要得到宝藏，请解出 $x$。

输入样例

本题单个测试点内包含多组测试数据。

输入第一行一个正整数 $T$ ($1 \leq T \leq 20$)，表示数据组数。

每组数据第一行一个正整数 $n$ ($1 \leq n \leq 10^5$)，表示方程数量。

接下来 $n$ 行，第 $i$ 行包含三个整数 $u_i, v_i, w_i$（$-10^9 \leq u_i, v_i, w_i \leq 10^9$，且 $u_i \neq 0, v_i \neq 0, w_i \neq 0$），意义如题。

保证单个测试点内每组数据中 $n$ 的和不超过 $10^6$。

输出样例

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

样例

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

3
3
0