K. I Wanna Maker
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Redcrown the Bear is a gamer who likes playing hardcore games such as I Wanna series. As an experienced player, he has also made many I Wanna levels by himself.

Redcrown is making a new level with a puzzle: given $$$\tilde{k},\tilde{x}$$$ and several consecutive positive integers from $$$l$$$ to $$$r$$$, the player needs to determine whether there exist $$$\tilde{k}$$$ different integers such that their sum is $$$\tilde{x}$$$. Now Redcrown needs to decide the range of the given integers in this level, denoted by the interval $$$[l,r]$$$. In addition to $$$0 \lt l \le r$$$, he wants to make the interval satisfy $$$n$$$ conditions, each of which is of one of the following two types:

  • 1 k x: there exist $$$k$$$ different integers within the interval $$$[l,r]$$$ such that their sum is $$$x$$$.
  • 2 k x: there do not exist $$$k$$$ different integers within the interval $$$[l,r]$$$ such that their sum is $$$x$$$. (There are two possible cases: there are less than $$$k$$$ integers in this interval; or, there are $$$k$$$ or more integers in this interval, but there are no $$$k$$$ integers whose sum is $$$x$$$.)

Redcrown wants to know the number of different intervals $$$[l,r]$$$ that satisfy the conditions.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$), indicating the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), indicating the number of conditions.

Each of the following $$$n$$$ lines contains three integers $$$t,k,x$$$ ($$$1 \le t \le 2$$$, $$$1 \le k \le 10^9$$$, $$$1 \le x \le 10^{9}$$$), indicating a condition.

It is guaranteed that $$$\sum n \le 10^5$$$ over all test cases.

Output

For each test case, output an integer in a single line indicating the number of different intervals that satisfy the conditions. If there are an infinite number of intervals, output $$$-1$$$ in a single line.

Example
Input
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
Output
4
-1
0
7
Note

For the first test case of the sample, there are two conditions:

  1. There exists an integer $$$2$$$ within the interval.
  2. There does not exist an integer $$$4$$$ within the interval.

There are four intervals that satisfy the conditions: $$$[1,2]$$$, $$$[1,3]$$$, $$$[2,2]$$$ and $$$[2,3]$$$.

For the second test case of the sample, there are two conditions:

  1. There exists an integer $$$4$$$ within the interval.
  2. There does not exist an integer $$$2$$$ within the interval.

All intervals with $$$3 \le l \le 4$$$ and $$$r \ge 4$$$ satisfy the conditions, so there are an infinite number of intervals.

$$$\quad$$$

Here is a reference picture of the I Wanna level: