As all programmers know, there are $$$n \times m$$$ ballerinas performing in a ballet, and their arrangement can be represented as a table with $$$n$$$ rows and $$$m$$$ columns. Each ballerina performs one of $$$26$$$ movements, which can be described by one of the English letters.

Choreographer Vadim wants to dispel this myth. To do this, he wants to stage a show in which all the ballerinas gracefully move to the opposite side of the stage from their starting positions. Programmers will find it easier to understand this movement as a $$$180^{\circ}$$$ rotation of the table. To maintain the sequence of visual storytelling in the ballet, the ballerinas perform this movement instantaneously, without stopping their movements, and the final arrangement is identical to the initial one.

Unfortunately, Vadim understands that with the current performance and the already planned arrangement of the ballerinas, such a maneuver will not be possible. Therefore, he is ready to invite more ballerinas to the performance. They can perform any movement and occupy any position, but they cannot stand between those already participating in a ballet. The most important thing is that in the end, a rectangular table is formed, possibly larger than the original one. Additionally, it is essential that at least one ballerina from the original arrangement moves to the position of one of the other ballerinas from the original arrangement or remains in her place. Please advise Vadim on the smallest number of ballerinas he will need to invite.

Input

Each test consists of several test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases. The following lines describe the test cases.

In the first line of each set, two integers $$$n$$$ and $$$m$$$ are given — the number of rows and the number of columns of the table $$$(1 \le n, m \le 10^6, 1 \le n \cdot m \le 10^6)$$$.

The next $$$n$$$ lines of length $$$m$$$ describe the movements of the ballerinas — the ballerina in the $$$i$$$-th row and $$$j$$$-th column performs the movement $$$f_{ij}$$$, where $$$f_{ij}$$$ — is a lowercase English letter.

It is guaranteed that the sum of $$$n \cdot m$$$ across all test cases does not exceed $$$10^6$$$.

Output

For each test case, output the minimum number of ballerinas that Vadim will need to invite.

Note

In the first sample, you can invite 4 ballerinas and arrange them as follows:

h	e	y	e	h
h	e	y	e	h

In the second sample, you can invite 16 ballerinas and arrange them like this:

j	k	a	b	c
k	j	d	e	f
i	h	g	h	i
f	e	d	j	k
c	b	a	k	j

In the third sample, you can invite 2 ballerinas and arrange them like this:

e	t
a	f
f	a
t	e

Here, the invited ballerinas are marked in bold.

Famous Choreographer

Examples