#P16775. [GKS 2020 #H] Retype

[GKS 2020 #H] Retype

Problem Description

After spending many hours studying for programming competitions, you decided to take a rest and play video games. You are currently playing an adventure game called Quick Start.

This game has NN levels, and you are currently on the KK-th level. Unfortunately, you just realized that to beat the boss at the final level, you will need a special sword, which can be picked up at level SS. You have already completed that level, but you forgot to pick up the sword at that level.

Now you want to pick up the sword and finish the game in the least amount of time possible, and for that you have two options:

  1. Restart the game and complete all levels again, starting from level 11.
  2. Move to previous levels until you reach level SS, pick up the sword and complete all the remaining levels, starting from level SS.

Every time you enter a level you have to exit it, either by completing it and going to the next level or by moving to a previous level or by finishing / exiting the game. Exiting any level takes 11 minute. That means, for example, that it took you LL minutes to complete the first LL levels.

Your task is to discover which option would result in the least amount of total time to finish the game (including the time you have already spent).

Input Format

The first line of the input gives the number of test cases, TT. TT test cases follow.

The first (and only) line of each test case contains three integers NN, KK and SS: the number of levels in the game, the current level you are in, and the level where you have to pick up the sword, respectively.

Output Format

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 11) and yy is the least amount of total time to finish the game.

2
10 5 2
10 7 6
Case #1: 15
Case #2: 12

Hint

In Sample Case #1, it took you 44 minutes to complete the first 44 levels and enter the 55-th level.

Restarting the game and completing all levels again would take 1111 more minutes (11 minute to restart and 1010 to complete 1010 levels), which adds up to 1515 minutes. The other option would be to move backwards until you reach level 22 (which would take 33 minutes), and then complete all the remaining levels (taking 99 more minutes), which would result in a total of 1616 minutes.

In Sample Case #2, it took you 66 minutes to complete the first 66 levels and enter the 77-th level.

Moving backwards until reaching level 66 (11 minute), and then completing all the remaining levels (55 minutes), would take a total of 1212 minutes to finish the game.

Limits

1T1001 \le T \le 100.

1S<K<N1 \le S < K < N.

Test Set 11

N1000N \le 1000.

Test Set 22

N109N \le 10^9.