【题目描述】
小K喜欢探险，他早就听说地下城里埋葬着一堆宝藏。为此，他历时多年收集资料，终于搞清楚宝藏的位置。
宝藏散落在地下城的一个矩形迷宫里。迷宫可以看成是一个n×m 的矩阵，共有 n×m 个方格，左上角（1,1）为入口，右下角（n,m）为出口。由于受到规则限制，小K只能向下或向右走，有些地方有陷阱，小K无法通过，必须要绕过这些陷阱。并且小K最多只能改变
k 次方向，否则就会触发禁制威胁到生命。小K把自己收集的宝藏地图交给了你，请你帮助小K计算从入口到出口一共有多少条不同的路线。如果一条路线中小K经过了某个方格而另一条路线中没有，则认为这两条路线不同。
【输入格式】
第一行一个整数 T
表示T 组输入数据；
每组输入数据：
第一行三个整数 n,m,k；接下来n 行，每行一个长度为m 的字符串，其中字符 .表示该位置安全可以走，
'#' 表示该位置有陷阱不能走。
【输出格式】
每组数据输出一行，一个整数，表示可以选择的不同路线数量。
