Cho xâu \(S\) và \(Q\) truy vấn. Mỗi truy vấn cho hai chỉ số \(l, r\) (đánh số từ 0 trong \(S\)), hãy in ra độ dài tiền tố chung dài nhất của hai xâu con bắt đầu tại \(l\) và \(r\).

Định dạng đầu vào

• Dòng 1: xâu \(S\).
• Dòng 2: số \(Q\).
• \(Q\) dòng tiếp: hai số \(l, r\).

Định dạng đầu ra

• Với mỗi truy vấn, in ra LCP của hai xâu con.

Ví dụ

Input:

abacaba
3
0 4
2 6
0 6

Output:

3
3
7

Ràng buộc

• 100% số điểm: \(|S| \le 10^5, Q \le 10^5\).