RP

小白成功通过考核了，这时候需要去和大boss见面，为了能够给大boss有个好印象，小白决定在公司的一些房间和同事交流攒RP，最后再去和大Boss见面。然而，RP不是那么好攒的，所以有可能会出现坏RP。他需要你的帮忙，在和大Boss见面后，尽可能的攒多RP。公司的房间是矩形排布的，你的起点在（1，1），而你需要走到（N,M）,为了尽快的和老板见面，你的时间并不多，你只能这么走：如果当前格子是（x,y），下一步可以是（x+1,y），(x,y+1)或者(x,y*k) 其中k是任意大于1的整数。

第一行输入T，表示有T组测试案例。每一组测试案例输出N M(1<=n<=20,10<=m<=1000)，表示有N行M列的矩阵。 下面有N行，每一行包含M个数值a ( |a|<100 )。

请对应每组测试数据输出一个整数，表示答案