Matcom Online Grader

Fito ha dejado la computación y quiere comenzar un negocio de venta y confección de collares. Uno de los productos que más aceptación tiene es un collar con el nombre del cliente. Fito tiene unas fichas con las letras del alfabeto para crear sus collares.

Un día uno de sus amigos como broma hizo una cadena con todas las letras que tenía Fito. A Fito esto no le hizo tanta gracia cuando se dio cuenta que todas las letras estaban pegadas y por tanto tendría que cortar cada una para separarlas. Para evitar esto Fito decide que cuando tenga una orden va a buscar en la gran cadena  si la palabra que quiere aparece como subcadena. En caso de aparecer Fito solo tiene que hacer dos cortes a lo sumo para obtener el collar pedido.

Fito también se da cuenta que una vez puestas las letras en un collar este se puede rotar para formar nuevas palabras (no se puede invertir porque las letras aparecen en un solo lado de las fichas). Con esta forma de trabajar Fito está seguro de poder cumplir cualquier encargo que le hagan, incluso de tener varias formas de hacerlo.

Nuestro tarea consiste en: dado el texto formado por la cadena de todas las letras y los pedidos que tiene Fito en un día, decir para cada uno de ellos la cantidad de formas en que Fito puede formar la palabra usando el método descrito anteriormente. Dos formas son consideradas distintas si Fito debe picar en posiciones diferentes la cadena de las letras.

La primera línea de la entrada tiene una cadena $S$ que representa la cadena con todas las letras. La cadena está formada por letras minúsculas del alfabeto latino y tiene tamaño a lo sumo $10^5$.  La segunda línea tiene un entero $N (1 \leq N \leq 1000)$ la cantidad de pedidos. Después le siguen $N$ líneas cada una con una palabra que debe formar Fito. La longitud total de las palabras es a lo sumo $10^6$.

Por cada pedido se debe imprimir en una línea la cantidad de formas en que Fito puede formar dicha palabra. Cada pedido es independiente.