UOFTBA - The Super Mario Blues

Because you somehow missed out on having a proper childhood, your friends are now forcing you to play a certain game for the first time - Super Mario Brothers. However, as a result of said missing-out, you find that you hate it. Who would want to go around as an Italian plumber, eating mushrooms and jumping on turtles, anyway? Needless to say, you want to get it over with as soon as possible.

From your understanding, there are 8 worlds (numbered from 1 to 8), each with 4 levels (numbered from 1 to 4). The $i$th level in the $j$th world is referred to by the string "j-i" (without the quotes). A player starts in level 1-1, with the objective of eventually completing level 8-4. In general, after completing each level, the player progress to the next level in the world (or, if it was the last level in the world, then to the first level in the following world). For example, the next level after 3-2 is 3-3, while the next one after 5-4 is 6-1.

However, there are also three hidden warp zones in the game, which allow the player to skip directly to the start of a later world after completing a certain level in a specific way. In particular, there is a warp zone from level 1-2 to worlds 2, 3, and 4, another from level 4-2 to worlds 6, 7, and 8, and a final one from level 4-2 to world 5. Because you're in a hurry, you'll be taking advantage of these whenever possible - this means that, after playing level 1-2, you'll skip to level 4-1, and after level 4-2, you'll skip to level 8-1.

You and your friends have $T$ ($1 \leq T \leq 50$) get-togethers. In each one, your friends play for a while and then hand you the controller, in addition to pointing a gun to your head in case you try to run away. Given which level you initially find yourself in, you'd like to determine how many levels you'll have to complete to get this thing over with.

Input

First line: 1 integer, $T$

For each get-together:

1 line with 3 characters, describing your starting level

Output

For each get-together:

1 integer, the number of levels you must pass to complete the game

Example

Input:
3
6-1
8-3
1-1 Output: 12
2
8

Explanation of Sample

In the first scenario, you have no choice but to complete every level in worlds 6, 7, and 8, for a total of $3 * 4 = 12$.

In the second scenario, you're already on the second-last level, so you only need to pass 8-3 and 8-4.

In the third scenario, you should play levels 1-1 and 1-2, warp to world 4, play 4-1 and 4-2, warp to world 8, and finally pass all of the stages there to finish the game. This amounts to 8 levels.


Added by:SourSpinach
Date:2013-05-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem, used in the 2012 UofT ACM Tryouts

hide comments
2013-05-21 10:15:28 Francky
Moved to tutorial.
2013-05-21 08:46:43 Haijun Deng
Just 10 minutes to AC this.
Please move this question to tutorial!
2013-05-21 06:32:02 coding_express
please move this question to tutorial,one of the easiest problem of spoj

Last edit: 2013-05-21 06:33:06
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.