描述

在我们的游戏收藏中，至少需要有一款经典的电脑游戏。这类游戏通常可以描述为"城镇追逐战"。在我们的案例中，一个名为Jack的笑脸角色正穿梭于被划分为若干小格子的城镇中。部分格子被墙壁覆盖，无法通行。Jack需要收集点数，并尽量避免与追逐他的怪物接触。一旦Jack吃到了特殊点$（即星号*）$，局势就会逆转——Jack可以吃掉怪物。如此循环往复。相信大家都曾见过这类游戏。

在我们的案例中，城镇是随机生成的。Jack总是从左上角出发，而"奖励星号"位于右下角。在最困难的关卡中，奖励会在恰好足够从左上角移动到右下角的步数后消失$（假设Jack只向右或向下移动）$。如果Jack走错一步，他将无法及时到达。但玩家仍需避免被怪物抓住，因此必须选择最优路径前往右下角。你需要计算存在多少条不同的可行路径。

输入

第一行是一个正整数$Z$，表示测试用例的数量。

每个测试用例的第一行是两个正整数$R$和$S$$（1 ≤ R, S ≤ 1000）$，分别表示城镇的行数和列数。

接下来的$R$行，每行包含$S$个字符。字符为#表示墙壁，.表示空地。左上角和右下角始终是空地。

输出

对于每个测试用例，输出一行："Existuje X ruznych cest."$（存在X条不同的路径）$，其中$X$是满足条件的路径数量。如果不存在可行路径，$X$为0。

输入样例1

2
3 3
...
.#.
...
1 6
...#..

输出样例1

Existuje 2 ruznych cest.
Existuje 0 ruznych cest.

样例解释

第一个测试用例：

$3x3$的城镇，中间有一个墙壁。

存在两条路径：右→右→下→下 或 下→下→右→右。

第二个测试用例：

$1x6$的城镇，中间有墙壁阻挡。

无法从左上角移动到右下角，路径数为$0$。

题目来源

CTU Open 1999