You are currently facing upcoming exams and find yourself in a large library with books arranged in a linear manner on a shelf. Your goal is to read books from left to right in the library, and you have two types of operations to perform:

• Type 1 operation: 1 x - This operation involves reading the next x books, starting from the current book and moving towards the right.
• Type 2 operation: Undo the last operation - This operation undoes the most recent reading operation. This allows you to go back to your previous reading point. When you perform an "Undo" operation, you return to the point in the book sequence where you initiated the last "Read" operation. It is useful for re-reading books you've already covered

At the end of your library session, tell what's the total number of unique books that you have revised at least once (i.e. read atleast twice). Please note that all the operations provided will be consistent, meaning you will not be given an undo operation that's invalid or impossible.

Input

• The first line of the input contains a single integer T corresponding to the number of test cases. The T test cases follow.
• The first line of each test case contains an integer N denoting total number of operations you need to apply.
• Each of the next N lines of the test case will contain an operation
  • If the operation is of type 1, then the line will contain two integers, i.e. 1, x.
  • If the operation is of type 2, then the line will contain only one integer, i.e. 2.

Output

• For each test case, output an integer corresponding to the total number of books that you have revised in the library session.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 10⁵
• 1 ≤ x ≤ 10⁴

Subtasks

Subtask #1

• 1 ≤ N ≤ 10

Subtask #2

• Original constraints

Sample

Input

3
4
1 2
1 3
2
1 4
4
1 2
2
1 4
2
6
1 3
1 5
1 6
2
2
1 7

Output

3
2
7

Explanation

For the test case 1,

• In the first operation, we read books 1 and 2.
• In the second operation, we read books 3, 4, 5
• In the third operation (which is an undo operation), we now go back to the first operation, i.e. we want to read books again, then we will start from reading book 3
• In the fourth operation, we read 4 books, i.e. book 3, 4, 5 and 6. The books 3, 4 and 5 are read twice, whereas the books 1, 2, 6 are read once. Thus, the number of books that you have revised at least once are 3 (i.e. 3, 4 and 5)

For the test case 2,

• In the first operation, you read books 1, 2
• In the second operation, you go back to start reading from book 1
• In the third operation, you read books 1, 2, 3, 4.
• In the fourth operation, you go back to reading from book 1.

You can see that the books 1, 2 are read at least twice and the books 3, 4 are read only once. Answer for this would be 2.