Uma sequência obtida removendo zero ou mais elementos de uma sequência chama-se subsequência dessa sequência. Por exemplo, aab é uma subsequência de $X=\texttt{ababca}$, mas não de $Y=\texttt{cbabba}$.

Uma subsequência que aparece nas duas sequências dadas chama-se subsequência comum de ambas. Por exemplo, para as sequências $X$ e $Y$ acima, baa é uma subsequência comum, mas aab não é.

Dada uma subsequência comum $W$ de duas sequências $X$ e $Y$, queremos determinar se $W$ pode ser expandida. Dizemos que $W$ é expansível se inserir um elemento numa posição de $W$ produz uma subsequência comum mais longa; caso contrário, não é expansível. Por exemplo, para as $X$ e $Y$ acima, a subsequência comum baa pode ser expandida para baba. No entanto, a subsequência comum ca não pode ser expandida mais.

Dadas duas sequências $X$, $Y$ e uma subsequência comum $W$ de ambas, escreve um programa que determine se $W$ é expansível.

Restrições

• Cada entrada contém entre $1$ e $100$ casos de teste a resolver.
• As somas de $|X|$ e de $|Y|$ são, cada uma, no máximo $200\,000$.
• $W$ é uma subsequência comum de $X$ e $Y$.
• As sequências contêm apenas letras minúsculas inglesas.

Subtarefas

1. (14 pontos) $|W| = 1$
2. (17 pontos) As somas de $|X|$ e de $|Y|$ são, cada uma, no máximo $300$.
3. (25 pontos) As somas de $|X|$ e de $|Y|$ são, cada uma, no máximo $20\,000$.
4. (44 pontos) Sem restrições adicionais.

Entrada

A primeira linha contém o número de casos de teste $T$.

As $3 \times T$ linhas seguintes contêm a informação dos casos de teste.

Cada caso consiste em três linhas que contêm as sequências $X$, $Y$ e $W$, respetivamente.

Cada sequência é dada como letras minúsculas inglesas consecutivas, sem espaços.

Saída

Para cada caso, imprime se é expansível, com um resultado por linha.

Imprime 1 se for expansível e 0 caso contrário.

Exemplos

Entrada 1

2
ababca
cbabba
baa 
aaabbbccc
caacbbc
ccc

Saída 1

1
0