在过去两年里，你认真对待了“K-Shaped Figures”和“H-Shaped Figures”这类题目。你做好了充分的准备，为剩下的 24 个字母推测了可能出现的题目，甚至实现了全部 24 个解法，并用尽了你的数字团队参考文档空间，只为了把这些代码带到比赛中。如果评委们如此缺乏创意，又出了一道关于字母形状的题目，你只需 1 分钟就能通过，让所有人感到困惑。

什么，又是形状题？真的吗？！哈哈！哦……等一下……

我们称平面上的两个圆构成一个“8 字形”，如果它们相切，但其中任何一个圆都不在另一个圆的内部。

左侧为有效的 8 字形，右侧为无效的 8 字形

给定平面上的一组 $n$ 个圆。任意两个圆的公共点不超过一个。换句话说，没有两个圆相交两次或重合，但它们可以相切或一个位于另一个内部。

请找出这组圆中构成 8 字形的圆对数量。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。

接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$，表示圆的数量 ($2 \le n \le 2 \cdot 10^5$)。

接下来的 $n$ 行中，第 $i$ 行包含三个整数 $x_i, y_i$ 和 $r_i$，表示第 $i$ 个圆的圆心坐标和半径 ($-10^9 \le x_i, y_i \le 10^9$; $1 \le r_i \le 10^9$)。保证任意两个圆不会相交两次或重合，但它们可以相切或一个位于另一个内部。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出构成 8 字形的圆对数量。

样例

样例输入 1

2
5
1 1 1
1 3 1
3 1 1
3 3 1
6 7 4
6
-3 0 3
-2 0 2
-1 0 1
1 0 1
2 0 2
3 0 3

样例输出 1

5
9