import java.util.* ;
public class Main {
public static void main
( String args
[ ] ) { Scanner sc
= new Scanner
( System .
in ) ; int n = sc.nextInt ( ) ;
while ( n-- > 0 ) {
int count = 0 ;
int x = sc.nextInt ( ) ;
StringBuilder sb = new StringBuilder( s) ;
int j = 0 ;
count = rabin_karp( str, s) .size ( ) ;
//more than 1
if ( count > 1 ) {
//no str in s
} else if ( count == 0 ) {
int i;
for ( i = 0 ; i < x; i++ ) {
while ( j < str.length ( ) && i < s.length ( ) && ( str.charAt ( j) == s.charAt ( i) || s.charAt ( i) == '?' ) ) {
if ( s.charAt ( i) == '?' )
sb.setCharAt ( i, str.charAt ( j) ) ;
i++;
j++;
}
if ( j >= str.length ( ) ) {
count++;
break ;
}
j = 0 ;
}
for ( ; i < sb.length ( ) ; i++ ) {
if ( sb.charAt ( i) == '?' )
sb.setCharAt ( i, 'd' ) ;
}
if ( count== 1 ) {
System .
out .
println ( sb.
toString ( ) ) ; }
else
} else {
for ( int i = 0 ; i < s.length ( ) ; i++ ) {
if ( s.charAt ( i) == '?' )
sb.setCharAt ( i, 'd' ) ;
}
System .
out .
println ( sb.
toString ( ) ) ; }
}
}
//find substring occurrence
int p = 31 ;
int m = ( int ) 1e9 + 9 ;
long S = s.length ( ) , T = t.length ( ) ;
Map
< Long , Long
> p_pow
= new HashMap
<> ( ) ; p_pow.put ( 0L, 1L) ;
for ( long i
= 1 ; i
< Math .
max ( S, T
) ; i
++ ) p_pow.put ( i, ( p_pow.get ( i - 1 ) * p) % m) ;
Map
< Long , Long
> h
= new HashMap
<> ( ) ; for ( long i = 0 ; i < T + 2 ; i++ )
h.put ( i, 0L) ;
for ( long i = 0 ; i < T; i++ )
h.put ( i + 1 , ( h.get ( i) + ( t.charAt ( ( int ) i) - 'a' + 1 ) * p_pow.get ( i) ) % m) ;
long h_s = 0 ;
for ( long i = 0 ; i < S; i++ )
h_s = ( h_s + ( s.charAt ( ( int ) i) - 'a' + 1 ) * p_pow.get ( i) ) % m;
List< Long> occurences = new ArrayList<> ( ) ;
for ( long i = 0 ; i + S - 1 < T; i++ ) {
long cur_h = ( h.get ( i + S) + m - h.get ( i) ) % m;
if ( cur_h == h_s * p_pow.get ( i) % m)
occurences.add ( i) ;
}
return occurences;
}
}
aW1wb3J0IGphdmEudXRpbC4qOwogCnB1YmxpYyBjbGFzcyBNYWluIHsKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZyBhcmdzW10pIHsKICAgICAgICBTY2FubmVyIHNjID0gbmV3IFNjYW5uZXIoU3lzdGVtLmluKTsKICAgICAgICBpbnQgbiA9IHNjLm5leHRJbnQoKTsKICAgICAgICB3aGlsZSAobi0tID4gMCkgewogICAgICAgICAgICBTdHJpbmcgc3RyID0gImFiYWNhYmEiOwogICAgICAgICAgICBpbnQgY291bnQgPSAwOwogICAgICAgICAgICBpbnQgeCA9IHNjLm5leHRJbnQoKTsKICAgICAgICAgICAgU3RyaW5nIHMgPSBzYy5uZXh0KCk7CiAgICAgICAgICAgIFN0cmluZ0J1aWxkZXIgc2IgPSBuZXcgU3RyaW5nQnVpbGRlcihzKTsKICAgICAgICAgICAgaW50IGogPSAwOwogICAgICAgICAgICBjb3VudCA9IHJhYmluX2thcnAoc3RyLCBzKS5zaXplKCk7CiAgICAgICAgICAgIC8vbW9yZSB0aGFuIDEKICAgICAgICAgICAgaWYgKGNvdW50ID4gMSkgewogICAgICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJObyIpOwogICAgICAgICAgICAvL25vIHN0ciBpbiBzCiAgICAgICAgICAgIH0gZWxzZSBpZiAoY291bnQgPT0gMCkgewogICAgICAgICAgICAgICAgaW50IGk7CiAgICAgICAgICAgICAgICBmb3IgKGkgPSAwOyBpIDwgeDsgaSsrKSB7CiAgICAgICAgICAgICAgICAgICAgd2hpbGUgKGogPCBzdHIubGVuZ3RoKCkgJiYgaSA8IHMubGVuZ3RoKCkgJiYgKHN0ci5jaGFyQXQoaikgPT0gcy5jaGFyQXQoaSkgfHwgcy5jaGFyQXQoaSkgPT0gJz8nKSkgewogICAgICAgICAgICAgICAgICAgICAgICBpZiAocy5jaGFyQXQoaSkgPT0gJz8nKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgc2Iuc2V0Q2hhckF0KGksIHN0ci5jaGFyQXQoaikpOwogICAgICAgICAgICAgICAgICAgICAgICBpKys7CiAgICAgICAgICAgICAgICAgICAgICAgIGorKzsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgaWYgKGogPj0gc3RyLmxlbmd0aCgpKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIGNvdW50Kys7CiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBqID0gMDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGZvciAoOyBpIDwgc2IubGVuZ3RoKCk7aSsrKSB7CiAgICAgICAgICAgICAgICAgICAgaWYgKHNiLmNoYXJBdChpKSA9PSAnPycpCiAgICAgICAgICAgICAgICAgICAgICAgIHNiLnNldENoYXJBdChpLCAnZCcpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaWYoY291bnQ9PTEpIHsKICAgICAgICAgICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIlllcyIpOwogICAgICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihzYi50b1N0cmluZygpKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIk5PIik7CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IHMubGVuZ3RoKCk7IGkrKykgewogICAgICAgICAgICAgICAgICAgIGlmIChzLmNoYXJBdChpKSA9PSAnPycpCiAgICAgICAgICAgICAgICAgICAgICAgIHNiLnNldENoYXJBdChpLCAnZCcpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJZZXMiKTsKICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihzYi50b1N0cmluZygpKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIC8vZmluZCBzdWJzdHJpbmcgb2NjdXJyZW5jZQogICAgc3RhdGljIExpc3Q8TG9uZz4gcmFiaW5fa2FycChTdHJpbmcgcywgU3RyaW5nIHQpIHsKICAgICAgICBpbnQgcCA9IDMxOwogICAgICAgIGludCBtID0gKGludCkgMWU5ICsgOTsKICAgICAgICBsb25nIFMgPSBzLmxlbmd0aCgpLCBUID0gdC5sZW5ndGgoKTsKIAogICAgICAgIE1hcDxMb25nLCBMb25nPiBwX3BvdyA9IG5ldyBIYXNoTWFwPD4oKTsKICAgICAgICBwX3Bvdy5wdXQoMEwsIDFMKTsKICAgICAgICBmb3IgKGxvbmcgaSA9IDE7IGkgPCBNYXRoLm1heChTLCBUKTsgaSsrKQogICAgICAgICAgICBwX3Bvdy5wdXQoaSwgKHBfcG93LmdldChpIC0gMSkgKiBwKSAlIG0pOwogCiAgICAgICAgTWFwPExvbmcsIExvbmc+IGggPSBuZXcgSGFzaE1hcDw+KCk7CiAgICAgICAgZm9yIChsb25nIGkgPSAwOyBpIDwgVCArIDI7IGkrKykKICAgICAgICAgICAgaC5wdXQoaSwgMEwpOwogICAgICAgIGZvciAobG9uZyBpID0gMDsgaSA8IFQ7IGkrKykKICAgICAgICAgICAgaC5wdXQoaSArIDEsIChoLmdldChpKSArICh0LmNoYXJBdCgoaW50KSBpKSAtICdhJyArIDEpICogcF9wb3cuZ2V0KGkpKSAlIG0pOwogICAgICAgIGxvbmcgaF9zID0gMDsKICAgICAgICBmb3IgKGxvbmcgaSA9IDA7IGkgPCBTOyBpKyspCiAgICAgICAgICAgIGhfcyA9IChoX3MgKyAocy5jaGFyQXQoKGludCkgaSkgLSAnYScgKyAxKSAqIHBfcG93LmdldChpKSkgJSBtOwogCiAgICAgICAgTGlzdDxMb25nPiBvY2N1cmVuY2VzID0gbmV3IEFycmF5TGlzdDw+KCk7CiAgICAgICAgZm9yIChsb25nIGkgPSAwOyBpICsgUyAtIDEgPCBUOyBpKyspIHsKICAgICAgICAgICAgbG9uZyBjdXJfaCA9IChoLmdldChpICsgUykgKyBtIC0gaC5nZXQoaSkpICUgbTsKICAgICAgICAgICAgaWYgKGN1cl9oID09IGhfcyAqIHBfcG93LmdldChpKSAlIG0pCiAgICAgICAgICAgICAgICBvY2N1cmVuY2VzLmFkZChpKTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIG9jY3VyZW5jZXM7CiAgICB9Cn0=