bin9638, người sẽ trở thành hokage vĩ đại nhất, vua hải tặc tương lai, kẻ thừa kế hơi thở mặt trời, mang trong mình sức mạnh của titan thủy tổ, người sở hữu dàn harem khủng nhất vũ trụ anime hiện đang có \(1\) kèo solo yasuo 20 ngày đêm với algorit. Sau \(1\) thời gian dài giao chiến nhưng vẫn chưa phân định thắng thua thì cả \(2\) quyết định phân biệt thắng thua bằng cách giải \(1\) bài toán.

Bài toán là cho \(1\) xâu \(S\) chỉ gồm các chữ cái latinh viết thường \(([S]\leq5000)\) và \(q\) truy vấn \((q\leq10^5)\), với mỗi truy vấn bạn phải trả lời xem đoạn \([l,r]\) của xâu \(S\) có bao nhiêu cặp xâu con bằng nhau. Xâu con của dãy \(S\) là \(1\) dãy kí tự liên tiếp không rỗng.

bin9638 sau cuộc chiến đã cạn hết sức lực nên đành nhờ các bạn giải giùm vậy. Hãy giúp bin9638 nhé !

Yêu cầu: hãy giải bài toán.

Input

• Dòng đầu là xâu \(S\), dòng thứ \(2\) là số \(q\).
• \(q\) dòng tiếp theo mỗi dòng là \(2\) số \(l,r\) \((1 \leq l \leq r \leq [S])\).

Output

• Gồm \(q\) dòng với mỗi dòng là đáp án cho truy vấn tương ứng.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \([S], q\leq100\).
• Subtask \(2\) (\(30\%\) số điểm): \([S], q\leq2000\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

abcabc
2
1 4
1 6

1
6

aaa
1
1 3

4