Cho một bảng kích thước ~n \times m~. Các dòng được đánh số từ ~1~ đến ~n~, các cột đánh số từ ~1~ đến ~m~. Mỗi ô ~(i, j)~ tại dòng ~i~ và cột ~j~ có một màu sắc tương ứng là ~c_{ij}~.

Khoảng cách Manhattan giữa hai ô ~(r_1, c_1)~ và ~(r_2, c_2)~ được tính bằng công thức:

$$d = \vert{}r_1 - r_2\vert{} + \vert{}c_1 - c_2\vert{}$$

Yêu cầu: Tính tổng khoảng cách Manhattan giữa tất cả các cặp ô có cùng màu với nhau trên bảng. Lưu ý các cặp ô không tính thứ tự.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n \le m~, ~n \times m \le 100\,000~) — số dòng và số cột của bảng.

~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên ~c_{ij}~ (~1 \le c_{ij} \le 100\,000~) — màu sắc của các ô trên bảng.

Output

In ra một số nguyên duy nhất — tổng khoảng cách Manhattan giữa mọi cặp ô cùng màu.

Scoring

Sample Input 1

2 3
1 2 3
3 2 1

Sample Output 1

7

Sample Input 2

3 4
1 1 2 2
2 1 1 2
2 2 1 1

Sample Output 2

76

Giải thích

Trong ví dụ đầu tiên, có ~3~ cặp ô có cùng màu với nhau:

• Cặp ô cùng màu thứ nhất: ~(1,1)~ và ~(2,3)~ — Khoảng cách Manhattan là ~\vert{}1-2\vert{} + \vert{}1-3\vert{} = 3~.
• Cặp ô cùng màu thứ hai: ~(1,2)~ và ~(2,2)~ — Khoảng cách Manhattan là ~\vert{}1-2\vert{} + \vert{}2-2\vert{} = 1~.
• Cặp ô cùng màu thứ ba: ~(1,3)~ và ~(2,1)~ — Khoảng cách Manhattan là ~\vert{}1-2\vert{} + \vert{}3-1\vert{} = 3~.

Tổng khoảng cách của các cặp ô cùng màu này là: ~3 + 1 + 3 = 7~.

Cho một xâu ký tự ~S~. Ta thực hiện chia xâu ~S~ thành ~k~ xâu con liên tiếp không rỗng: ~s_1, s_2, \dots, s_k~ sao cho khi ghép chúng lại theo đúng thứ tự, ta thu được xâu ban đầu (tức là ~S = s_1 + s_2 + \dots + s_k~).

Cách chia này được gọi là đối xứng nếu dãy các xâu con tạo thành một cấu trúc đối xứng (palindrome). Nói cách khác, xâu con thứ ~i~ từ đầu phải giống hệt xâu con thứ ~i~ từ cuối, hay:

$$s_i = s_{k - i + 1} \quad \forall 1 \le i \le k$$

• Ví dụ, với xâu "decode", ta có hai cách chia đối xứng sau:
• Chia thành ~3~ phần: (de)(co)(de) (vì xâu con thứ nhất "de" bằng xâu con thứ ba "de").
• Chia thành ~1~ phần: (decode) (mọi xâu luôn có ít nhất cách chia mặc định này với ~k = 1~).

Yêu cầu: Cho một xâu ~S~, hãy tìm cách chia đối xứng sao cho số lượng xâu con ~k~ thu được là lớn nhất.

Input

Dòng đầu tiên chứa số nguyên ~T \le 5~ — số lượng bộ dữ liệu thử nghiệm (test case).

~T~ dòng tiếp theo, mỗi dòng chứa một xâu ~S~ chỉ gồm các chữ cái tiếng Anh viết thường và không chứa khoảng trắng.

Output

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất trên một dòng — số lượng xâu con lớn nhất ~k~ của cách chia đối xứng tìm được.

Scoring

Trong các subtask, ~T \le 5~ và gọi ~L~ là độ dài của xâu ~S~ ứng mỗi test case.

Sample Input 1

5
decode
deleted
sicthaui
amanaplanacanalpanama
jokerqueenqueenjoker

Sample Output 1

3
5
1
21
4

Giải thích

• Ví dụ đầu tiên đã được giải thích trong đề bài.
• Ở ví dụ thứ hai, xâu "deleted" có cách chia đối xứng dài nhất gồm ~5~ phần: (d)(e)(let)(e)(d).