Redcrown the Bear 是一位喜欢玩《I Wanna》系列等硬核游戏的玩家。作为一名经验丰富的玩家，他也亲自制作了许多《I Wanna》关卡。

Redcrown 正在制作一个包含谜题的新关卡：给定 $k$ 和 $x$，以及从 $l$ 到 $r$ 的若干连续正整数，玩家需要确定是否存在 $k$ 个不同的整数，使得它们的和为 $x$。现在，Redcrown 需要确定该关卡中给定整数的范围，记为区间 $[l, r]$。此外，在满足 $0 < l \le r$ 的前提下，他希望该区间满足 $n$ 个条件，每个条件属于以下两种类型之一：

• $1\ k\ x$：在区间 $[l, r]$ 内存在 $k$ 个不同的整数，使得它们的和为 $x$。
• $2\ k\ x$：在区间 $[l, r]$ 内不存在 $k$ 个不同的整数，使得它们的和为 $x$。（有两种可能的情况：区间内整数个数少于 $k$ 个；或者区间内有 $k$ 个或更多整数，但不存在和为 $x$ 的 $k$ 个整数。）

Redcrown 想知道有多少个不同的区间 $[l, r]$ 满足这些条件。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示条件的数量。 接下来的 $n$ 行，每行包含三个整数 $t, k, x$ ($1 \le t \le 2, 1 \le k \le 10^9, 1 \le x \le 10^9$)，表示一个条件。 保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示满足条件的区间数量。如果存在无穷多个区间，则输出 $-1$。

样例

输入格式 1

4
2
1 1 2
2 1 4
2
1 1 4
2 1 2
2
1 1 1
2 1 1
4
2 1 15
1 5 20
1 3 8
2 2 25

输出格式 1

4
-1
0
7

说明

对于样例中的第一个测试用例，有两个条件：

1. 区间内存在整数 2。
2. 区间内不存在整数 4。

满足条件的区间有四个：$[1, 2], [1, 3], [2, 2]$ 和 $[2, 3]$。

对于样例中的第二个测试用例，有两个条件：

1. 区间内存在整数 4。
2. 区间内不存在整数 2。

所有满足 $3 \le l \le 4$ 且 $r \ge 4$ 的区间都满足条件，因此有无穷多个区间。

以下是《I Wanna》关卡的参考图片：

Choose 3 blocks to make sum = 16