Mountain Tour (Large)

You are on top of Mount Everest, and you want to enjoy every hiking trail up there. Wandering around Mount Everest alone is a bad idea, because you can get lost in the dark. So you only take tours that leave at fixed times with a guide.

The mountain has $C$ camps, numbered 1 through $C$, and $2C$ one way hiking tours, numbered 1 through $2C$. Each tour starts at one camp, finishes at a different camp, and passes through no other camp in between. Mount Everest is sparsely populated and business is slow. Exactly 2 tours depart from each camp, and exactly 2 tours arrive at each camp.

Every tour runs daily. Tours 1 and 2 start at camp 1, tours 3 and 4 start at camp 2, and in general tour $2i - 1$ and tour $2i$ start at camp $i$. Tour $i$ ends at camp $E_i$, leaves at hour $L_i$, and takes exactly $D_i$ hours.

It is now hour 0, and the hours of a day are numbered 0 through 23. You are at camp 1, and you want to take every tour exactly once and end up back at camp 1. You cannot travel between camps except on a tour. While you are in a camp you may wait for any number of hours, including zero, but you can start a tour only at the instant it departs.

The schedules make the goal reachable. You want to finish as fast as possible. Plan the route optimally and report how many hours it takes to finish all of the tours.

The first line holds the number of test cases $T$. Each test case begins with one line holding the integer $C$, the number of camps. Then $2C$ lines follow. The $i$-th of those lines, counting from 1, describes one tour that starts at camp $\lfloor (i+1)/2 \rfloor$ and holds three integers $E_i$, $L_i$, $D_i$. This format guarantees that exactly two tours start at each camp.

Limits

• $1 \le T \le 100$
• $2 \le C \le 1000$
• $1 \le E_i \le C$
• $E_i \ne \lceil i/2 \rceil$ for all $i$, so no tour starts and ends at the same camp
• $|\{ j : E_j = v \}| = 2$ for every camp $v$, so exactly two tours end at each camp
• $0 \le L_i \le 23$
• $1 \le D_i \le 1000$
• At least one route starts at camp 1, uses every tour exactly once, and returns to camp 1

For each test case, print one line of the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of hours needed to reach the goal.

In the first test case, the optimal plan is the following.

• Wait at camp 1 for an hour, until it becomes hour 1.
• Leave camp 1 at hour 1 on the 5 hour tour, and arrive at camp 2 at hour 6.
• Leave camp 2 at hour 6 right away on the 3 hour tour, and arrive at camp 1 at hour 9.
• Wait at camp 1 for 15 hours, until it becomes hour 0 of the next day.
• Leave camp 1 at hour 0 on the 3 hour tour, and arrive at camp 2 at hour 3.
• Wait at camp 2 for an hour, until it becomes hour 4.
• Leave camp 2 at hour 4 on the 4 hour tour, and arrive at camp 1 at hour 8.

That reaches the goal in 1 day and 8 hours, which is 32 hours. Every other plan takes longer.

In the second test case, all of the tours leave at the same hour and take the same time. After finishing any tour you can start another one right away. If the tours are numbered 1 through 8 in the order they appear in the input, one optimal plan is 1, 5, 4, 7, 6, 2, 3, 8.