Dado un texto \(s\) y un diccionario de palabras, di si \(s\) se puede partir en una secuencia de una o más palabras del diccionario. Una misma palabra se puede usar varias veces.

Entrada

La primera línea tiene \(T\) \((1 \le T \le 20)\). Cada caso viene en tres líneas: el texto \(s\) \((1 \le |s| \le 300)\); la cantidad de palabras \(m\) \((1 \le m \le 1000)\); y las \(m\) palabras distintas, de largo entre \(1\) y \(20\). Todo es de letras minúsculas.

Salida

Para cada caso, true si el texto se puede partir o false si no.

Ejemplo 1

Entrada

3
leetcode
2
leet code
applepenapple
2
apple pen
catsandog
5
cats dog sand and cat

Salida

true
true
false

Ejemplo 2

Entrada

1
aaaaaaa
2
aaaa aaa

Salida

true

Basado en el problema 139 de LeetCode, Word Break, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.