Cơ quan an ninh không gian mạng thu thập được một chuỗi tín hiệu mã hóa \(S\) bao gồm các chữ cái in thường. Để giải mã, họ cần phân tích sự đa dạng của các mẫu tín hiệu con trong các khoảng thời gian khác nhau.
Bạn được yêu cầu trả lời \(Q\) truy vấn độc lập. Mỗi truy vấn cung cấp hai số nguyên \(L\) và \(R\), bạn cần tính xem có bao nhiêu chuỗi con phân biệt (distinct substrings) nằm trọn vẹn trong đoạn \(S[L \dots R]\).

Input

• Dòng đầu tiên chứa chuỗi \(S\) có độ dài \(N\).
• Dòng thứ hai chứa số nguyên dương \(Q\) là số lượng truy vấn.
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L\) và \(R\) mô tả một truy vấn.
• \(1 \le N, Q \le 10^5\)
• \(1 \le L \le R \le N\)

Output

• In ra \(Q\) dòng, mỗi dòng là một số nguyên duy nhất — số lượng chuỗi con phân biệt của đoạn \(S[L \dots R]\).

Example

ababa
4
1 5
2 4
1 3
3 5

9
5
5
5