Crime House (Small)

Time limit5sMemory limit512 MB

Summary
Assign each masked passage to a person so inside and outside states stay valid and report the smallest possible final occupancy, or CRIME TIME.
Level

Medium6 of 10

Topics
Backtracking, Simulation
Solved
No attempts yet

Problem

You work for the police, and you have found a house that people use for committing crimes. Everyone calls it the Crime House. One day you mount a camera above the front door and record everyone who passes through it.

You do not know how many people were inside when the day began. You are also not sure whether the front door is the only way in and out. The people going in and out are criminals, so some of them wear a mask, and the recording does not show who those people are.

Sometimes you can guess who was behind a mask. Suppose criminal 5 enters, then a masked person leaves, then criminal 5 enters again. Either the masked person was criminal 5, or the house has another way out.

Someone who is already inside cannot enter, and someone who is already outside cannot leave. At the end of the day, after the house closes its doors for the night, you watch the recording. You are an optimist, so you want to know whether the recording can be explained with the front door as the only entrance and exit. If it can, you want the smallest number of people who could be inside at the end of the day.

Input

The first line holds the number of test cases TT. The test cases follow. Each test case starts with a line holding one integer NN, the number of times people pass through the front door during the day. The next NN lines hold one passage each, in the order they were recorded.

Each of those lines holds a single character, E or L, then a space, then an integer idid. E means someone entered through the front door and L means someone left through it. If idid is greater than zero, the person with that identifier passed through. If idid is zero, the person who passed through wore a mask and you do not know who it was. A masked person can be anyone, including someone whose identifier never appears in the recording.

Limits

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤151 \le N \le 15
  • 0≤id≤20000 \le id \le 2000

Output

For each test case, print one line in the form Case #x: y, where x is the test case number starting from 1. If it is possible that the front door is the only entrance and exit, y is the smallest number of people who could be inside the house at the end of the day. If it is impossible, y is CRIME TIME.

Examples2

  1. Example 1

    Input
    5
3
E 5
L 0
E 5
2
L 1
L 1
4
L 1
E 0
E 0
L 1
7
L 2
E 0
E 1
E 2
E 0
E 3
L 4
13
L 4
L 1
L 2
E 0
L 1
E 0
L 2
E 0
L 2
E 0
E 0
L 1
L 4
    Expected output
    Case #1: 1
Case #2: CRIME TIME
Case #3: 1
Case #4: 4
Case #5: 0

  2. Example 2

    Input
    3
1
E 0
1
L 0
2
E 7
L 7
    Expected output
    Case #1: 1
Case #2: 0
Case #3: 0