H

Pairing Boys and Girls

Input: Standard Input

Output: Standard Output

 

In a dance party, Boys and Girls make a line before a song starts. Then a boy will pair up with a girl who is somewhere later in the line. The pairing will occur in such a way that number of pairs get maximized.

 

For example: If the Boy-Girl sequence in a line looks like: GGBGGBGB then there can be 2 pairs maximum. If we consider the line to be 1 indexed, the boy standing at 3rd position pairs up with the girl at 4th or 5th position and the boy at 6th position will pair up with the girl at 7th position. They boy at 8th position can not propose any girl, since there is no girl after him. Again, the boy at 3rd position could not pair up with the girl at 7th position, because if he would have paired up with her the number of pairing would be only 1, which is not maximum possible pairing.

 

After each song, boys and girls would line up in the same way before a new song. In this time, bunch of boys or girls may come. Manager will insert them at a certain position in the line. Then again pairing will occur. After each insertion you have to print number of maximum possible pairings. Initially there would be a boy in the line.

 

Input

First line of the input file will contain a positive integer T (T ≤ 10). Hence follow T test cases.

 

In the first line of each test case there will be a positive integer N (N ≤ 100,000). Each of the next N lines describes an insertion operation for a group. Each line will contain 3 integers “type where count”.

·       type is 0 if the group is of boys, type will be 1 if the group is of girl.

·       where denotes the position where this group will be inserted. If where = 0, then this group will be inserted in front of the entire line, otherwise that group will be inserted after where number of people. It will not exceed total number people in the line.

·       count denotes number of boys/girls in that group. 1 ≤ count ≤ 10,000

 

Output

For each case output the case number “Case x:”. Hence for each insertion operation, output the maximum possible pairing after the insertion operation is performed. There will be no blank line between output for different test cases. For details please go through the sample input output.

 

Sample Input                                 Output for Sample Input

2

3

1 1 4

0 3 3

0 0 2

1

1 0 1

 

Case 1:

1

3

4

Case 2:

0

 

Problemsetter: Md. Mahbubul Hasan, Special Thanks: Tasnim Imran Sunny