Determine the Unsafety of NFP Cryptocurrencies

An NFP is a cryptocurrency whose value over \(s\) days is represented by a character matrix of \(r\) rows and \(s\) columns containing only the characters . and #. For the \(i\)th column, scanning from bottom to top, the first occurrence of # is used to determine the value for day \(i\). Formally, if the \(j\)th character from the bottom in the \(i\)th column is #, then the value on day \(i\) is \(j\). The "unsafety" of an NFP is defined as the difference between the maximum and minimum values it attains over the \(s\) days, i.e., \(\text{unsafety} = \max_{1 \le i \le s} v_i - \min_{1 \le i \le s} v_i\), where \(v_i\) is the value on day \(i\).

You are given \(n\) NFPs. For each NFP, the first line contains two integers \(r\) and \(s\). The following \(r\) lines each contain a string of length \(s\) representing the matrix. The top-most input line represents the top row of the matrix, and the bottom-most line is the bottom row. It is guaranteed that each column contains at least one #.

For each NFP, output its unsafety on a new line.

inputFormat

The first line contains a single integer \(n\) representing the number of NFPs. For each NFP, the first line contains two integers \(r\) and \(s\) where \(r\) is the number of rows and \(s\) is the number of days (columns). Then follow \(r\) lines, each containing a string of length \(s\) composed of characters . and #, representing the matrix from the top row to the bottom row.

outputFormat

For each NFP, output a single integer on a new line representing its unsafety (i.e., the difference between the maximum and minimum values over the \(s\) days).

sample

1
4 7
....##.
#..#...
.##....
......#

3