Square Distance

////  main.cpp//  bc87-1002////  Created by Candy on 10/1/16.//  Copyright © 2016 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <vector>#include <string>using namespace std;const int N=1005,V=1e6+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}    return x;}int T,n,m,l,d[N][N];//dao xuchar s[N],t[N];void dp(){    memset(d,0,sizeof(d));    d[l+1][0]=1;    for(int i=l;i>=1;i--)        for(int j=0;j<=m;j++){            if(s[i]==s[i+l]) {                d[i][j]|=d[i+1][j];                if(j>=2) d[i][j]|=d[i+1][j-2];            }else{                if(j>=1) d[i][j]|=d[i+1][j-1];                if(j>=2) d[i][j]|=d[i+1][j-2];            }            //printf("d %d %d %d\n",i,j,d[i][j]);        }    if(!d[1][m]){printf("Impossible\n");return;}    int res=m;    for(int i=1;i<=l;i++)        for(int k=0;k<26;k++){            int tmp=(s[i]-‘a‘!=k)+(s[i+l]-‘a‘!=k);            if(d[i+1][res-tmp]){                t[i]=t[i+l]=k+‘a‘;                res-=tmp;                break;            }        }    for(int i=1;i<=n;i++) putchar(t[i]);    putchar(‘\n‘);}int main(int argc, const char * argv[]) {    T=read();    while(T--){        n=read();m=read(); l=n/2;        scanf("%s",s+1);        dp();    }    return 0;}