TLPNGEM - Teleporters and Gems

Duck is playing "Teleporters and Gems". On a 1 x N map, there may be multiple teleporters (or no) and at least one gem. At the beginning, Duck is standing at the most left position. He has to collect all the gems with the help of teleporters. Below are the rules:

1. Moving 1 unit is counted as 1 move.

2. When Duck reaches a teleporter, he can instantly reach any of the next 3 teleporters (eg. 1 to 2, 3 or 4 teleporter, but not 1 to 5, 6, 7 teleporter, and previous not allowed) by 3 moves; Or he can ignore that teleporter and keep moving to next cell which is counted as 1 move.

Let '@' = Teleporter, '.' = empty cell, there are 4 teleporters: @.@..@@, if Duck is at position 0 (the 1st teleporter), then he can instantly reach 2nd, 3rd or 4th teleporter by 3 moves. But ignoring the 1st teleporter makes him reach 2nd teleporter by 2 moves.

3. Duck has to collect all gems.

4. Once he collects the last gem, the game ends and no more move needed.

5. Duck can only move right.

Can you help him find out the minimum number of moves in order to collect all gems?

Input

The first line is the number of test cases T. (1 ≤ T ≤ 50)

For each test case, there is a string S consisting of '.' (≥ 0), '@' (≥ 0) and '*' (≥ 1), representing empty cell, teleporter and gem. (1 ≤ |S| ≤ 104)

Output

Print one integer x where x is the minimum number of moves in order to collect all gems starting from the most left cell.

Example

Input:
3
.@@...@.@...@@..*@.@.*...@..
....@...@@.**.@....@@@*@.
.*....*@@@@*..@@*..@

Output:
14
16
16

Explanation

Bracket means cells that Duck will pass through and minimum number of moves to that cell
Case 1: (.@@)...@.@...(@@..*@.@.*)...@.. = 0 1 2 -> 5 6 7 8 9 10 11 12 13 14
Case 2: (....@)...@(@.**.@)....@@(@*)@. = 0 1 2 3 4 -> 7 8 9 10 11 12 -> 15 16
Case 3: (.*....*@)@@(@*..@@*)..@ = 0 1 2 3 4 5 6 7 -> 10 11 12 13 14 15 16


Added by:him0727
Date:2018-11-08
Time limit:0.600s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own problem

hide comments
2022-09-22 11:46:36 Sushovan Sen
@psetter : Can you please check my solution? I am unable to find any bug
Edit -> NVM, found bug

Last edit: 2022-09-23 06:11:31
2019-11-15 02:18:14
Hmm, assert passes on at least one '*' being present in input string, for me.
2019-03-11 14:57:35 Simes
There's still a test case with no gems. I was getting WA until I handled it, then confirmed it with Asserts.

Edit: My mistake!

Last edit: 2022-03-13 13:37:04
2018-11-16 08:28:52 Simes
@him0727. Perhaps the problem statement should mention that for the benefit of those people who don't read the comments. Item 1 says nothing about not moving left.

RE:
Thanks for suggestion. But I think item 2 "go to next 3 teleporters or next cell" implies we can only move right.

Last edit: 2018-11-16 17:49:09
2018-11-13 04:49:14 Oleg
Can Duck move left ? i.e what is answer for .@..........*@

RE:
When Duck reaches "@", he has two choices: either go to any of next 3 teleporters or to next cell, so he can only move forward. In your example, the answer is 12.

Last edit: 2018-11-13 14:34:30
2018-11-09 22:30:43
1. Either there are cases with no gems, or the input is malformed;
2. It has been pointed out to you several times the stupid TLs you set prevents solving not only in interpreted languages, but basically anything else than C. Do you derive some sick fun from wasting people's time?

RE:
1. One test case was no gems indeed and fixed, thanks
2. You just left a comment in problem "MAPEXC", how come you say several times
3. I accept all well meant criticisms, so the TL is changed
4. If you really think answering my problems is wasting time, I suggest you to skip all my problems or just to disqualify your solutions, thanks

[NG]: Thanks for fixing the textcases and correcting TL. My Python solution now gets AC in 0.23s, which is the same algo that my C which got 0.00s. I hope this shows why I'm generally so pissed with unreasonable limits. Not every problem can be set for every language without allowing suboptimal solutions, but this isn't one of them.

Also got AC with updated TL in MAPEXC which seemed an excellent problem when I got on it 8 months ago, but brought me only frustration for non-trivial effort required to code it. You didn't respond to my comment then and I have been ignoring your problems ever since. Probably just mulled angry thoughts instead of repeating myself under every problem ;)

Last edit: 2018-11-11 23:24:03
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.