Description

Let's say that two circles on a plane form an $\textit{8-shaped figure}$ if they touch each other, but neither of them lies inside the other one.

You are given a collection of $n$ circles on the plane. No two circles have more than one common point. In other words, no two circles intersect twice or coincide, but they can touch or lie one within another.

Find the number of pairs of circles from this collection that form an 8-shaped figure.

Input Format

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$, denoting the number of circles ($2 \le n \le 2 \cdot 10^5$).

The $i$-th of the following $n$ lines contains three integers $x_i$, $y_i$, and $r_i$, denoting the coordinates of the center of the $i$-th circle and its radius ($-10^9 \le x_i, y_i \le 10^9$; $1 \le r_i \le 10^9$). No two circles intersect twice or coincide, but they can touch or lie one within another.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output Format

For each test case, print the number of pairs of circles that form an 8-shaped figure.

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