URI Online Judge | 2814

Loud Music

By Felipe C. Ochial, URI BR Brazil

Timelimit: 1

Marcelo Freitas de Jesus, known as Little Fred likes carnival a lot. During the holiday he intends to listen to music at the highest possible volume. However, to do so he needs to consider the location of his neighbor Josué Braulio Petiz, who always has a noise dosimeter (device to measure the intensity of sound) around and will call the police if the sound is even a hundredth over the maximum permitted by Babanua’s law. Given the simplified map of the neighbor where F represents Little Fred’s house, J represents Josué’s house, X represents a random house and each character represents 10 meters ( consider that Little Fred is emiting the sound from the center of his terrain and Josué is measuring the sound in the center of his terrain), the maximum sound permited in Babanua and considering that the sound propagate with 1% loss for each meter and that the sound maintain it’s intensity in that meter ( physics laws are different in Babanua, by the presidential decree of R.Rey) inform the maximum volume which Little Fred can listen to his music.

To calculate the value, one must divide the maximum allowed value by 0.99 in the exponent of how many times the sound will be reduced. For example, in the case of a maximum sound of 110Dbs and a distance of 14,1421 we will have that the maximum sound is 110 / 0.9914, that is, 126,619.

Input

The input consist of an integer N (0 < N < 51) which informs the number of test cases. Each test case is composed by two integers K (0< K < 201 ) and J ( 0 < J < 30 ), which indicates the maximum sound intensity and the number of lines used to draw the map respectively. After follows J lines (with a maximum of 30 characters) representing the map.

Output

To each test case print the maximum sound intensity which Little Fred can listen to, with no decimal places, rounded down, followed by “dBs”.

Input Sample Output Sample

3

110 2

XF

JX

70 5

XXXXX

FXXXX

XXXXJ

XXXXX

XXXXX

140 10

XXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXX

XXXXXXFXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXJXXXX

XXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXX

126 dBs

105 dBs

360 dBs