The television at the boy's home contains the channels from 1 to n inclusive. The father wanted to avoid his son to watch some channels in the Television. You are given k unique channels that are banned by the father.
For example assume that the TV contains 25 channels and the father bans the channels 15, 17 and 18 and you are currently at channel 16. If you press the 'down' button in the remote,  you will move to channel 14 and if you press the 'up' button in the remote, you will move to channel 19. Also if you press up button from channel 25 you will move to channel 1 and if you press down button from channel 1 you will move to channel 25.
There are 13 buttons in the remote as shown in the figure.

To move to a channel you can press the digits of the channel or you can use Up/Down/Previous buttons. The previous button will take you to the immediately previous channel you watched. (The previous button does not take effect until you have moved to some other channel after the first one.)

The remote control responds to delays. So you can take the button presses "1" and "9" either as a way to go to channel 1 and then to channel 9, or to channel 19 directly.

You are given the sequence of channels that the boy wanted to watch. Find the minimum number of remote button presses required by the boy. It's not necessary to watch the given channels consecutively, but it is necessary to watch them in the order specified. (In other words, the given sequence must be a subsequence of the optimal channel series the boy chooses to watch.)

To watch the first channel in the sequence, you must press the digits of the channel.


The first line consists of and integer t, the number of test cases. Each test case consists of 4 lines. The first line consists of 2 integers n and k, the number of channels in the remote and the number of channels blocked. The next line consists of k unique integers - the id of the blocked channels. The next line consists of an integer m the number of channels the boy wants to watch followed by a line with m integers - the channel id's of the channels that the boy wants to watch.


For each test case print the minimum number of remote button clicks required.

Input Constraints:




ChannelToWatch[i] != ChannelToWatch[i-1]

ChannelToWatch[any] != BannedChannel[any]

Sample Input:


5 0



1 2 3 4 5

500 0



140 160 139 160

5 2

2 4


1 3 5 3 5

Sample Output:

Case #1: 5

Case #2: 9

Case #3: 5


Note: Suppose you are currently at channel 6 and press up button twice you will move to channel 8. Now if you click on previous button, you will move to channel 7 and not channel 6.

Exlanation of Case #2:

The moves are "1", "4", "0", "down", "1", "6", "0", "previous", "previous"


Congrats and thanks to Mitch Schwartz for solving this problem first and for helping on setting test cases for this problem.

Added by:cegprakash
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF GOSU

hide comments
2013-02-27 20:27:39 Jimmy
Isn't there any restriction on the number of submits? Contestant "GAP" has made a very long queue of his submissions :(
2013-02-27 20:22:19 N.R.Samarasekara
What the hell GAP .. you screwed the system :((((
2013-02-27 19:16:51 Mathan Kumar
what happen if i click prev prev?? will it return the same channel or will it go to previous of previous channel??

reply: same

Last edit: 2013-02-27 19:33:50
2013-02-27 18:52:33 Paulo Cezar [UFG]
- What happens if I press the digits related to a blocked channel?

Reply: Assume that nothing happens. They are just unnecessary button presses.

Last edit: 2013-02-28 11:23:16
2013-02-27 18:36:32 GAP
Reply: can a banned channel appear in the son's wanted list?

Last edit: 2013-02-27 18:38:20
2013-02-27 18:27:45 Sanchit M. Bhatnagar
"To watch the first channel in the sequence, you must press the digits of the channel." so your minimum answer is at least that. You start at channel "nothing" so to speak.
2013-02-27 18:22:14 Erik Grabljevec
Do we start on channel 0 ?
2013-02-27 18:13:35 Sanchit M. Bhatnagar
I hope its something simple like that Patryk. Cause I'm pretty sure I have this question correctly coded :\

I even coded one with a random sequence of channel viewings. upon looking at his example. But it has been confirmed that the channels needed to be viewed in the same sequence. So.. yeah.

Last edit: 2013-02-27 18:15:28
2013-02-27 17:38:26 Patryk Kowalczyk
Should the output be of the following form:
Case #1: x_1
Case #2: x_2
Case #t: x_t

Or should it look like this one:

Reply: The output format is same as the sample output

Last edit: 2013-02-27 18:19:40
2013-02-27 17:26:42 cegprakash
same sequence
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.