何老板的公司生产了一种机器人，可以用于在运动会后清理运动场上的垃圾。在机器人开始工作前，给出了一张网格状的地图，每个包含垃圾的格子都被标记上了“G”。所有的机器人一开始都位于西北方的那一角，在工作结束时所有的机器人都会走到东南方的那一角。每个机器人只能往东和往南两个方向行走。一走到有垃圾的格子，机器人就会把垃圾清理掉。一旦机器人走到了东南方那一个角，它就会自动切断电源，不能再次工作。

你的任务是计算出最少需要多少个机器人，就能清理完所有的垃圾。
例如下图：所有的机器人一开始在(1,1)位置，结束时在(6,7)位置

下图展示了两种可能的方案，其中第二种方案更好，因为它只用了两个机器人。

由一行或多行构成，每行两个空格间隔的整数，表示一个包含垃圾的格子坐标
输入由0 0 作为结束。

注：每组测试数据的格子坐标是按行由小到大的顺序给出。

地图的行数和列数都不超过24

若干行，每行一个整数，表示对应测试数据的结果。

何某翻译