Bài tập

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\).

\begincenter

\endcenter

\begincenter

\endcenter

Example

2
0 0 0 1 1 1
0 0 0 2 2 2

8

Mùa World Cup vừa rồi là một mùa World Cup thú vị, kịch tính và đầy bất ngờ; có thể nói World Cup 2022 là kì World Cup hay nhất lịch sử, đặc biệt là với cộng đồng ̶̶R̶̶i̶̶c̶̶o̶̶n Sicon. Có lẽ với bin9638 thì đó là một kì World Cup không mấy vui vẻ. Sau khi đã cược hết tiền tiết kiệm vào Đức, ô tô vào Bỉ, laptop và điện thoại vào Tây Ban Nha, đặc biệt là sổ đỏ vào T1, bin9638 đã mất tất cả. Ngỡ rằng sẽ đi nhảy cầu giống như bao con người khác, nhưng bin9638 lại là người không dễ dàng từ bỏ. Vì vậy bin9638 đã tham gia giải cờ vua thế giới để kiếm tiền thưởng bù lại khoản lỗ.

bin9638 đánh với một bàn cờ đặc biệt gồm \(n\) hàng và \(m\) cột, ban đầu ở hàng thứ nhất anh ấy đặt một con mã ở vị trí bất kì. Mỗi nước đi con mã chỉ có thể tiến lên phía trước và đi theo hình chữ L giống như cờ vua. Giả sử con mã đang ở ô \((1;3)\) thì chỉ được đi tới ô \((2;1), (2;5), (3;2)\) hoặc \((3;4)\), ngoài ra con mã cũng không được đi ra ngoài bàn cờ. Tuy nhiên vì bàn cờ của bin9638 dùng là một bàn cờ siêu cổ, từ thời Napoleon đánh cầu lông ăn tiền nên bàn cờ có \(k\) ô đã bị hỏng, tức là không thể đặt quân cờ trên đó.

Bây giờ bin9638 muốn tính xem có bao nhiêu cách đi để đưa con mã tới hàng cuối cùng ( hàng \(n\) ), nhưng vì mải đi chơi với các bạn nữ ̶t̶̶r̶̶o̶̶n̶̶g̶ ̶m̶̶ơ nên anh ấy đành nhờ các bạn giải giúp vậy !

Input

Một dòng gồm \(3\) số nguyên dương \(n,m\) và \(k\).

\(k\) dòng tiếp theo mỗi dòng là \(2\) số nguyên dương \(x, y (x ≤ n, y ≤ m)\) biểu thị ô \((x;y)\) đã bị hỏng.

Output

Gồm một số duy nhất là kết quả khi chia lấy dư cho \(10^9 + 7\).

Example

2 3 2
1 1
2 2

1

4 4 2
3 4
4 4

10

Scoring

Subtask \(1\) (\(20\%\) số điểm): \(n ≤ 10^5, m ≤ 50, k ≤ 50\).

Subtask \(2\) (\(20\%\) số điểm): \(n ≤ 10^{18}, m ≤ 50, k = 0\).

Subtask \(3\) (\(30\%\) số điểm): \(n ≤ 10^{18}, m ≤ 10, k ≤ 50\).

Subtask \(4\) (\(30\%\) số điểm): \(n ≤ 10^{18}, m ≤ 50, k ≤ 50\).