问题描述

Yipeng有一头非常聪明的奶牛,这头奶牛有一个强烈的愿望就是去上学,yipeng决定同意他的请求。奶
牛的出发地是左下角坐标(1,1),学校坐标为右上角(m, n),这里我们只考虑整数点坐标。奶牛要
从左下走到右上,每次只能向右或向上走一个单位,即穿过一条道路。有一些坐标是不可到的,有一些
是可以到达的。Yipeng想考考这个聪明的奶牛,就问它每天上学一共有多少种不同的路径可以选择?两
条路径不同当两条道路至少有一条非公共道路。

问题输入

首先一个整数t表示测试数据组数(1=<t<=30),对每组数据都有两个整数m, n (1<=m, n<=15)表示学校
的坐标,然后是m*n的矩阵,第i行第j个数代表坐标为(i,j)处的坐标是不是可达,1代表可达,0代
表不可达。数据保证起点和终点可达。

问题输出

每组测试数据输出一行,每行一个整数,表示奶牛可以选择的上学路径数。如果没有路径能让奶牛上学
则输出0。

样例输入

1
4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

样例输出

20