题目描述

若平面上的两个圆相切，并且其中任何一个圆都不位于另一个圆的内部，则称这两个圆构成一个“8”字形图案。

上图左侧为合法的“8”字形图案，右侧为不合法的情形。

给定平面上的 $n$ 个圆。任意两个圆至多有一个公共点。换句话说，任意两个圆不会交于两个点，也不会重合，但它们可能相切，或者一个圆位于另一个圆内部。

请计算有多少对圆构成“8”字形图案。

输入格式

每个输入包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数。

对于每组测试数据：

• 第一行包含一个整数 $n$，表示圆的数量；
• 接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i,y_i,r_i$，分别表示第 $i$ 个圆的圆心坐标和半径。

保证任意两个圆不会交于两个点，也不会重合，但它们可以相切，或一个位于另一个内部。

数据范围

所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每组测试数据，输出构成“8”字形图案的圆对数量。

样例

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

5
9