Bài tập

\begincenter

\endcenter

Một xâu được gọi là xâu đối xứng nếu đọc xâu đó từ trái sang phải hoặc đọc từ phải sang trái đều như nhau. Ví dụ: "aaa", "abccba", "kk" là xâu đối xứng. Còn "abc", "coco", "nero" không là xâu đối xứng.

Cho một xâu \(S\) độ dài \(N\) chỉ chứa các kí tự từ a đến z. Mỗi giây, có thể xóa một xâu con của xâu \(S\), sao cho xâu con được xóa là một xâu đối xứng. Ví dụ, đối với xâu "nerokakakcontest", nếu ta xóa đi xâu con "kakak" thì xâu sẽ trở thành "nerocontest". Ta không thể xóa đi xâu con "nero" vì đây không phải là một xâu đối xứng. Xâu con của một xâu được định nghĩa là một đoạn các kí tự liên tiếp ở xâu ban đầu.

Hỏi cần ít nhất bao nhiêu giây để xóa toàn bộ xâu?

Input

Dòng đầu tiên ghi một số nguyên dương \(T\) \((T \leq 5)\) số lượng bộ dữ liệu đầu vào.

\(T\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(S\) tương ứng với bộ dữ liệu thứ \(i\).

Output

Ghi ra \(T\) dòng, dòng thứ \(i\) ghi ra thời gian ít nhất để xóa toàn bộ xâu của dữ liệu thứ \(i\).

Example

3
aabcbda
abba
addbcba

3
1
2

Scoring

\(50\%\) số test tương ứng với \(50\%\) số điểm có \(|S| \leq 16\).

\(50\%\) số test còn lại \(|S| \leq 300\).

Hôm nay là ngày đầu tiên đi học của Sơn, ở trường cô giáo dạy cho Sơn về các phép toán cộng trừ giữa các con số. Một kiến thức mới khiến Sơn cảm thấy rất hào hứng đó là phép toán tính khoảng cách hai số. Khoảng cách 2 số được xác định bằng tổng chênh lệch giữa các chữ số tương ứng của 2 số đó. Nếu 1 số có số lượng chữ số ít hơn số còn lại thì ta xem như thêm các số 0 ở phía trước.

Ví dụ:

• Khoảng cách hai số 4561 và 3278 bằng \(|4-3|+|5-2|+|6-7|+|1-8|=12\).

• Khoảng cách hai số 32 và 5678 bằng \(|0-5|+|0-6|+|3-7|+|2-8|=21\).

Bố của Sơn muốn kiểm tra xem con mình có khả năng tính toán siêu cấp hay không nên đã đưa ra một vấn đề liên quan đến phép toán khoảng cách hai số. Cho hai số nguyên dương \(L,R\) hãy tính tổng khoảng cách của tất cả cặp số \((A,B)\) thỏa mãn \(L\leq A\neq B\leq R\). Tuy là một người ra đề bài nhưng bố Sơn cũng không biết kết quả là bao nhiêu, vì vậy nhờ bạn hãy tính toán kết quả chia lấy dư cho \(10^9+7\) của bài toán trên và gửi lại cho bố Sơn.

Input

• Một dòng duy nhất gồm \(2\) số nguyên dương \(L,R\) (\(L\leq R\leq 10^{50000}\)).

Output

• In ra số nguyên là kết quả bài toán chia lấy dư cho \(10^9+7\).

Example

288 291

76

Scoring

• Subtask 1 (\(25\%\)): \(L,R\leq 10000\).

• Subtask 2 (\(30\%\)): \(L,R\leq 10^{100}\).

• Subtask 3 (\(45\%\)): Không có giới hạn gì thêm.

Cho bảng chữ kích thước \(m \cdot n\), mỗi ô chứa một kí tự \(A\) hoặc \(B\). Một hình chữ nhật con của bảng được gọi là bảng đẹp bậc \(k\) nếu số lượng kí tự \(A\) và số lượng kí tự \(B\) trong bảng con chênh lệch không quá \(k\).

Yêu cầu:
Cho bảng chữ kích thước \(m \cdot n\) và số nguyên \(k\), hãy tìm bảng con là bảng đẹp lớn nhất.

Input

• Dòng đầu chứa số nguyên \(T(T \leq 5)\) là số bộ dữ liệu.

• \(T\) nhóm dòng sau, mỗi dòng mô tả một bộ dữ liệu có dạng:

• Dòng đầu chứa ba số nguyên \(m, n, k\).

• \(m\) dòng tiếp theo, mỗi dòng chứa một xâu kí tự độ dài \(n\) chỉ gồm kí tự \(A\) hoặc \(B\).

Output

• Ghi ra thiết bị ra chuẩn \(T\) dòng, mỗi dòng chứa một số là số lượng ô trong bảng tìm được
  tương ứng với dữ liệu vào.

Example

2
3 4 0
AAAA
BBBB
BAAA
3 4 1
AAAA
BBBB
BAAA

8
9

Scoring

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 100\).

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 2000\).

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 40000, k = 0\).

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 60000\).