E - ノイズ除去

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたはプログラマーとしてとある会社に勤めています。

この会社であなたは、ユーザーから集めた文字列のある連続した部分に指定した文字列が含まれるかを判定する業務をしています。

例えば、文字列 rhd は文字列 thisisrhdcontest に含まれていますが、文字列 thanks や文字列 ratheads には含まれていません。

しかしながら、ユーザーからの問い合わせにより、不要な文字がノイズとしてユーザーから寄せられた文字列に入ってしまいユーザーの希望通りの判定が行われていないことが判明しました。

そこであなたは、以下の Q 個のクエリ 1 から Q を処理するプログラムを作成することになりました。

クエリ i : 「文字列 S_i と文字列 T_i が与えられる。いくつかの文字 x_1, x_2, ... , x_k を選び (1 文字も選ばなくても良い)、文字列 S_i から選んだ文字をすべて取り除くという操作を行って得られる文字列 S'_i として考えられるものの中に文字列 T_i が含まれうるか判定せよ」

例えば、S_1 = ratheads, T_1 = rhd のとき、S_1 から文字 a, e, t を取り除いたときに得られる文字列 S'_1 = rhds には文字列 T_1 = rhd が含まれるため、文字列 T_1 は含まれうるといえます。


入力

入力は以下の形式で標準入力から与えられる。

Q
S_1 T_1
S_2 T_2
:
S_Q T_Q
  • 1 行目には、クエリの個数 Q (1 ≦ Q ≦ 5,000) が与えられる。
  • 2 行目から Q 行には、クエリに関する情報が与えられる。このうち i (1 ≦ i ≦ Q) 行目には半角小文字英字のみで構成される 2 つの文字列 S_i, T_i (1 ≦ |S_i| ≦ 50, 1 ≦ |T_i| ≦ 50) が空白区切りで与えられる。

出力

Q 行にわたって出力せよ。Q 行のうち i (1 ≦ i ≦ Q) 行目には、クエリ i に対する答えを出力せよ。もしもクエリ i において文字列 T_i が含まれうるなら YES を、そうでないなら NO を出力せよ。出力の末尾にも改行を入れること。


入力例1

4
ratheads rhd
thisisrhdcontest rhd
yes no
abba aba

出力例1

YES
YES
NO
NO

クエリは 4 つあります。

  • クエリ 1 は、問題文中の例に示されています。S_1 から文字 a, e, t を取り除いたときに得られる文字列 S'_1 = rhds には文字列 T_1 が含まれるので、YES と出力します。
  • クエリ 2 では、文字列 S_2 から文字を取り除かなくても文字列 S_2 に文字列 T_2 が含まれるので YES を出力します。
  • クエリ 3 では、文字列 S_3 からどのように文字を取り除いても文字列 S'_3 に文字列 T_3 が含まれないので NO を出力します。
  • クエリ 4 では、文字列 S_4 からどのように文字を取り除いても文字列 S'_4 に文字列 T_4 が含まれないので NO を出力します。

なお、文字を指定してその文字を取り除くとき、指定した文字を一部取り除かずに残すことができないことに注意してください。


入力例2

5
abcdef bdf
aabbccdd b
abcabcabc aaba
abcdcba dba
ababababa aba

出力例2

YES
YES
NO
YES
YES