Description
The time now is 12 noon and Indiana Jones is standing on the western bank of a river. He wants to reach the eastern bank as fast as possible. Across the river is a series of stones, arranged in a straight line, and each stone is 1 meter away from its immediate neighbours or the two river banks.
Let us divide the time into intervals of one minute each, such that Interval 0 starts at 12:00:00, Interval 1 starts at 12:01:00, and so on. At the start of each interval, Indiana Jones can hop once from a stone/river bank to any stone/bank that is not more than 1.5 meters away, or stay put. He can hop so fast that we assume the time taken per hop is negligible.
The tricky part is this: The stones may sink and resurface! Within a time interval, a stone may sink at the middle of the interval, remains submerged and may resurface at the middle of another interval. If Indiana Jones is standing on a sinking stone, he will drown. Of course, Indiana Jones cannot hop to a stone that is submerged. At 12 noon, all stones are above the water and Indiana Jones is ready to hop. He has already derived the pattern of sinking/resurfacing for each stone during the next few intervals. Our task is to find the fastest way to cross the river.
Figure 1 shows an example of sinking and resurfacing stones over time. The example contains three stones, each of which is first sinking, then resurfacing and then sinking. The fastest way for Indiana Jones to cross the river is shown as a black line.
Input
The input consists of a line containing the number c of datasets, followed by c datasets, followed by a line containing the number `0'.
The first line of each dataset contains two positive integers, separated by a blank. The first value s is the number of stones. The second value t is the number of intervals whose movement pattern Indiana Jones can predict. You can assume 1 ≤ s ≤ 500 and 1 ≤ t ≤ 500 . The following t lines of each dataset describe the behavior of the stones in each interval. The i -th line describes the behavior of the stones in Interval i , where 0 ≤ i < t . Within each line, there are s characters, separated by blanks. The j -th character indicates the movement of the j -th stone in the middle of the i -th interval as follow:
``s":
The stone is sinking.:
``r":
The stone is resurfacing.:
``u":
The stone is not moving.:
Output
The output consists of one integer, which indicates the earliest interval at the beginning of which Indiana Jones can reach the eastern bank. If there is no way Indiana Jones can cross the river within t minutes, the output should be `-1'. Note that Indiana Jones actually has t + 1 chances to hop.
Notes for the sample: In this dataset, the fastest way to cross over is as follows:
- Stay put at the beginning of Interval 0.
- Stay put at the beginning of Interval 1.
- Stay put at the beginning of Interval 2.
- Jump from the western bank to the first stone at the beginning of Interval 3.
- Jump from the first stone to the second stone at the beginning of Interval 4.
- Jump from the second stone to the third stone at the beginning of Interval 5.
- Jump from the third stone to the eastern bank at the beginning of Interval 6.
Thus, Indiana Jones can reach the eastern bank the earliest at the beginning of Interval 6.