Una frase es un palíndromo si, después de pasar todas las mayúsculas a minúsculas y de borrar todo lo que no sea letra o dígito, se lee igual de izquierda a derecha que de derecha a izquierda. Una frase que queda vacía cuenta como palíndromo.

Para cada frase, di si es un palíndromo.

Entrada

La primera línea tiene \(T\). Cada una de las siguientes \(T\) líneas tiene una frase de caracteres ASCII imprimibles (puede contener espacios, pero no empieza ni termina con uno). La suma de los largos es a lo más \(2 \cdot 10^5\).

Salida

Para cada frase, true si es un palíndromo o false si no.

Ejemplo 1

Entrada

3
A man, a plan, a canal: Panama
race a car
?!

Salida

true
false
true

Ejemplo 2

Entrada

2
0P
ab_a

Salida

false
true

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