L. Lulu and Friends
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Let's put on our thinking caps! Hmm... hmmhmm, hmmhmm... ah, I got it! — Lulu

As the sun rose over Runeterra, Lulu the yordle skipped through the land, always on the lookout for magic and adventure. Today, she discovered something extraordinary — a glowing thread nestled in the roots of an ancient tree.

"This must be the Legendary String $$$T$$$!" Lulu gasped, remembering the tales of its magical properties. Holding the string, Lulu's mind flooded with memories of her adventures and the friends she'd met along the way.

But this wasn't just a simple discovery. The string held a puzzle, one tied to the names of her friends. Lulu could feel the magic in the air, urging her to solve it. For each of her friends names, she needs to solve this problem, "What's the minimum number of characters you need to delete from the legendary string $$$T$$$, so that it will contain her friend's name as a substring or determine if it's impossible?".

She turned to you, her eyes sparkling. "I need your help to figure this out! Let's unlock its secrets together!"

*A substring of string $$$s$$$ is a continuous segment of letters from $$$s$$$. For example, eter is a substring of runeterra and era is not.

Input

First line contains a legendary string $$$T$$$$$$(1 \leq |T| \leq 20) $$$, consisting of lowercase letters of the English alphabet.

The next line contains a single integer $$$Q$$$ $$$(1 \leq Q \leq 100,000)$$$, the number of her friends.

Then $$$Q$$$ lines follow, in the $$$i^{th}$$$ line $$$s_i$$$$$$(1 \leq |s_i| \leq 20)$$$, the name of the $$$i^{th}$$$ friend, is given. The names consist of lowercase letters of the English alphabet.

Output

Output $$$Q$$$ lines, the $$$i^{th}$$$ is the minimum number of characters you need to delete from the legendary string $$$T$$$ so that it will contain the $$$i^{th}$$$ friend's name as a substring or $$$-1$$$ if it's impossible.

Example
Input
leiulocuuniapnax
9
lulu
leona
lux
lilia
lucina
pix
lillia
icp
icpc
Output
4
7
9
7
9
-1
-1
8
-1
Note

In the first name, it's possible to delete the underlined characters, leiulocuuniapnax and it will contain the name as a substring in the underlined part luluuniapnax.

In the third name, it's possible to delete the underlined characters, leiulocuuniapnax and it will contain the name as a substring in the underlined part leiulux.

In the sixth and seventh names, it's impossible to delete characters from string T to make it containing pix or lillia as a substring, so the outputs are $$$-1$$$.