홍준이는 문자열을 좋아합니다. 그래서 문자열과 관련된 여러 문제들을 고민하고 있습니다.</p>

그 중 하나는 문자열 S가 주어졌을 때, 어떤 두 문자열 A와 B를 모두 포함하는 S의 연속 부분 문자열 중 가장 길이가 짧은 것을 구하는 문제입니다. 홍준이는 똑똑해서 이 문제를 금방 풀어버렸습니다. 그래서 한층 더 어려운 문제를 생각하였습니다. 두 문자열 A와 B가 질문 Q번 들어올 때에는 어떻게 빠르게 답을 구할 수 있을지 고민하던 홍준이는 너무 어려워서 A와 B의 길이가 짧다면 빨리 풀 수 있을 것으로 생각하고 있습니다.

홍준이를 도와 문제를 해결하는 프로그램을 작성하세요.

입력 형식

첫째 줄에 길이가 5만 이하인 문자열 S가 주어집니다.</p>

둘째 줄에 0 이상 10만 이하인 하나의 정수 Q가 주어집니다.

셋째 줄부터 Q개의 줄에 걸쳐 길이가 1 이상 4 이하인 두 문자열 A와 B가 주어집니다.

모든 문자들은 영문 알파벳 소문자로 구성되어 있습니다.

출력 형식

Q개의 줄에 걸쳐 각각의 두 문자열 A와 B를 부분 문자열로 가지는 S의 연속 부분 문자열의 최소 길이를 출력합니다. 만약 그런 연속 부분 문자열이 존재하지 않는다면 -1을 출력합니다.

예제 입력

xudyhduxyz
3
xyz xyz
dyh xyz
dzy xyz

예제 출력

3
8
-1