Dãy tình yêu là dãy chỉ gồm hai ký tự < và 3. Tuy nhiên, lạ ở chỗ, nếu có ai đó đọc phép lên dãy thì những phép màu sẽ xảy ra:

• Ký tự < được xếp liền trước ký tự 3 sẽ biến thành một trái tim nhỏ, có độ lớn là \(1\).
• Hai trái tim được xếp liền nhau sẽ biến thành một trái tim lớn hơn, có độ lớn là tổng độ lớn của hai trái tim cũ.
• Một trái tim có ký tự liền trước là < và ký tự liền sau là 3 sẽ trở thành một trái tim lớn hơn, với độ lớn tăng lên một đơn vị.

Những phép màu sẽ xảy ra liên tục và chỉ kết thúc khi nào những phép màu đó không còn tác động và làm thay đổi được dãy nữa.

Ví dụ:

• Dãy <3 sẽ tạo thành trái tim có độ lớn là \(1\).
• Dãy <3<3 sẽ tạo thành trái tim có độ lớn là \(2\).
• Dãy <<33 sẽ tạo thành trái tim có độ lớn là \(2\).
• Dãy <<3<3<333<3 sẽ tạo thành hai trái tim có độ lớn lần lượt là \(4\) và \(1\).

Hân là một cô phù thủy dễ thương và vô cùng tỉ mỉ. Với những dãy tình yêu, trước khi đọc phép, Hân sẽ bỏ đi một vài ký tự để đảm bảo cho trái tim có độ lớn lớn nhất trong dãy sau khi đọc phép là lớn nhất có thể.

Ví dụ với dãy <<3<3<333<3 Hân sẽ xóa đi ký tự 3 ở vị trí thứ \(8\) để dãy trở thành <<3<3<33<3. Sau khi đọc phép, dãy này sẽ tạo thành trái tim có độ lớn là \(5\), cũng là trái tim có độ lớn lớn nhất có thể tạo thành từ dãy ban đầu.

Hỏi với một dãy tình yêu \(T\) là một dãy con liên tiếp của dãy \(S\) cho trước, nếu để Hân đọc phép, trái tim lớn nhất có thể hình thành sẽ có độ lớn bao nhiêu?

Input

• Dòng đầu tiên chứa một dãy \(S\) \((|S| \leq 10^{6})\).
• Dòng thứ hai chứa một số \(Q\) \((Q \leq 10^{6})\) là số lượng truy vấn.
• \(Q\) dòng tiếp theo, mỗi dòng chứa 2 số \(l\) và \(r\) \((1 \leq l \leq r \leq |S|)\) thể hiện một truy vấn.

Output

• In ra độ lớn của trái tim lớn nhất mà Hân có thể tạo ra từ dãy con của \(S\) từ \(l\) đến \(r\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(|S| \leq 10\).
• Subtask \(2\) (\(20\%\) số điểm): \(Q = 1\).
• Subtask \(3\) (\(25\%\) số điểm): \(|S|, Q \leq 10^{5}\).
• Subtask \(4\) (\(25\%\) số điểm): Không có rằng buộc gì thêm.

Example

<<33<3<<333<<3<3
4
1 4
3 7
1 12
5 16

2
1
5
5