本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn

1356. Gluing Pictures


Description

Enzo recently traveled to the city of Montevideo, where he saw a big sign with the name of the city. He decided to take pictures of the sign to make a collage and send it to his friend Demonio. Enzo wants to form the name of his friend by taking one or several pictures of sections of the sign. For example, with the string "MONTEVIDEO", he might form the name of his friend by putting together "DE-MON-I-O", using four pictures to form the entire name. It is easy to show that the result cannot be achieved with fewer pictures.

You will be given the name of a city and a list of friends' names. Return the minimum number of pictures needed to form the name of each friend. When forming the names, pictures cannot be rotated, re ected or modified in any way.

Input

The  first line contains a string \$C\$ indicating the name of the city. The second line contains  a positive integer \$N\$ representing the number of friends. Each of the following \$N\$ lines contains a string indicating the name of a friend. All strings are non-empty and consist only of uppercase letters. The sum of the lengths of all strings is at most \$2 \times 10^5\$.

Output

Output \$N\$ lines, each line with an integer indicating the minimum number of needed pictures to form the corresponding name in the input, or the value "-1" if it is not possible to generate the name.

Samples

Input Copy
MONTEVIDEO
4
DEMONIO
MONTE
EDIT
WON
Output
4
1
4
-1
Input Copy
SANTIAGO
3
TITA
SANTIAGO
NAS
Output
3
1
3

Source

ICPC Latin American Regional 2019
Problem Information

Time Limit: 3000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 8 / 8
Tags:
Contests involved

1039. ICPC Latin American Regional 2019
My history solutions

You didn't submit any solution!
Submit your solution

Login Register