The race track is a straight line with starting point at Track[0] and ending point at Track[n-1]. The car is initially at Track[0].

Track[i]='#' if the track has a wall at Track[i].

The car can move from Track[i] to Track[i+1] if and only if Track[i+1] is not a wall. The time taken to move from Track[i] to Track[i+1] is 1 unit.

If there is a wall at Track[i+1], you can shoot it from Track[i] if you have enough bullets in the car. Once a bullet is fired, the bullets count will decrease by 1. The time required to fire a bullet is 0.

It is also allowed to ride the car off the track. It's allowed to move from Track[i] to offTrack[i], from offTrack[i] to offTrack[i+1] and from offTrack[i] to Track[i] (if Track[i] is not a wall). The time taken for any of these steps is 2 units.

Find the fastest possible time to finish the race. Print "Impossible" if it's impossible to finish the race.

Input

The first line consists of an integer t, the number of test cases. For each test case, the first line consists of two integers the length of race track n and the number of bullets the car can fire followed by a line with a string representing the Track.

Output

For each test case, print the expected result as specified in the problem statement.

Constraints

1 ≤ t ≤ 100

2 ≤ n ≤ 1000

0 ≤ bullets ≤ 1000

Track[i] ∈ {'S','E', '0', '#'}

Track[0]='S', Track[n-1]='E'

Example

Input:
10
7 3
S00000E
2 2
SE
4 1
S00E
8 1
S0000##E
8 3
S0#00#0E
7 2
S0#0##E
10 4
S00#0#0##E
5 2
S000E
7 1
S0##00E
9 0
S0000##0E

Output:
6
1
3
13
7
12
9
4
12
15