Minimum Substring Concatenation

Given a main string \(S\) and a list of words, your task is to determine for each word the minimum number of substrings of \(S\) (where each substring is a contiguous segment of \(S\)) that can be concatenated in order to form the word. If it is not possible to form the word by concatenating substrings from \(S\), output \(-1\) for that word.

Formally, for each word \(W\) of length \(n\), find the minimum positive integer \(k\) such that

[ W = s_1 + s_2 + \cdots + s_k, ]

where each (s_i) is a substring of (S). If no such segmentation exists, return (-1) for that word.

Example:

Input:  S = "abcdefg", words = ["abc", "cde", "age"]
Output: [1, 1, -1]
Explanation: "abc" and "cde" can be found as contiguous substrings in S, while "age" cannot be formed.

</p>

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains the main string \(S\).
2. The second line contains an integer \(N\) representing the number of words.
3. Each of the following \(N\) lines contains a single word.

outputFormat

Output \(N\) integers in one line separated by spaces. Each integer represents the minimum number of substrings required to form the corresponding word using substrings of \(S\), or \(-1\) if it is not possible.

## sample

abcdefg
3
abc
cde
age

1 1 -1

</p>