> #include <bits/stdc++.h>
> using namespace std;
> #define inf 999999
> char str[1003];
> int dp[3][1002][1003];
> int last = -1;
> int n;
> int solve(int x,int y,int bul)
> {
> if(y == n-1)
> {
> if(x == 1)
> return 0;
> else
> if(str[y-1] == '#')
> {
> if(bul > 0)
> return 2;
> else
> return inf;
> }
> return 2;
> }
>
> int &ret = dp[x][y][bul];
> if(ret != -1)
> return ret;
>
>
>
> if(x == 1)
> {
> if(str[y+1] != '#')
> return 1+solve(x,y+1,bul);
> else
> if(bul > 1 || (bul > 0 && last == y+1))
> return 1+solve(x,y+1,bul-1);
> else
> if(bul > 0)
> return 4+solve(x+1,y+1,bul);
> else
> if(last == n-2)
> return inf;
> else
> return 4+solve(x+1,y+1,bul);
> }
> else
> {
> if(str[y+1] != '#' && y+1 != n-1)
> return 1+min(3+solve(x-1,y+1,bul),1+solve(x,y+1,bul));
> else
> if(bul > 0 && last == y+1)
> return 4+solve(x-1,y+1,bul-1);
> else
> return 2+solve(x,y+1,bul);
> }
> }
> int main()
> {
> int t;
> scanf("%d",&t);
> while(t--)
> {
> memset(dp,-1,sizeof dp);
> int b;
> scanf("%d%d",&n,&b);
> for(int i=0;i<n;++i)
> {
> scanf(" %c",&str[i]);
> if(str[i] == '#')
> last = i;
> }
> int res = solve(1,0,b);
> if(res < inf)
> printf("%d\n",res);
> else
> puts("Impossible");
> }
> return 0;
> }