#ifndef INCLUDED_MAIN #define INCLUDED_MAIN #include __FILE__ #include #include using namespace atcoder; using mint = modint1000000007; int main(void){ int t; cin >> t; for(;t--;){ int h, w; cin >> h >> w; vector> a(h,vector(w)); int i,j; rep(i,h) rep(j,w) cin >> a[i][j]; bool ans = false; rep(i,h){ rep(j,w){ vector> v(h,vector(w,-1e17)); queue> q; q.push({i,j}); v[i][j] = a[i][j]; while(!q.empty()){ auto [x,y] = q.front(); q.pop(); int k; rep(k,h){ if(k==x) continue; if(v[k][y] + v[x][y] + a[k][y]> 0){ ans = true; break; }else if(v[k][y] < v[x][y] + a[k][y]){ v[k][y] = v[x][y]+a[k][y]; q.push({k,y}); } } rep(k,w){ if(k==y) continue; if(v[x][k] + v[x][y] + a[x][k]> 0){ ans = true; break; }else if(v[x][k] < v[x][y] + a[x][k]){ v[x][k] = v[x][y]+a[x][k]; q.push({x,k}); } } int nx = x+1, ny = y+1; while(0<=nx && 0<=ny && nx 0){ ans = true; break; }else if(v[nx][ny] < v[x][y] + a[nx][ny]){ v[nx][ny] = v[x][y] + a[nx][ny]; q.push({nx,ny}); } nx++;ny++; } nx = x+1; ny = y-1; while(0<=nx && 0<=ny && nx 0){ ans = true; break; }else if(v[nx][ny] < v[x][y] + a[nx][ny]){ v[nx][ny] = v[x][y] + a[nx][ny]; q.push({nx,ny}); } nx++;ny--; } nx = x-1; ny = y-1; while(0<=nx && 0<=ny && nx 0){ ans = true; break; }else if(v[nx][ny] < v[x][y] + a[nx][ny]){ v[nx][ny] = v[x][y] + a[nx][ny]; q.push({nx,ny}); } nx--;ny--; } nx = x-1; ny = y+1; while(0<=nx && 0<=ny && nx 0){ ans = true; break; }else if(v[nx][ny] < v[x][y] + a[nx][ny]){ v[nx][ny] = v[x][y] + a[nx][ny]; q.push({nx,ny}); } nx--;ny++; } if(ans) break; } if(ans) break; } if(ans) break; } if(ans){ cout << "infinite\n"; }else{ cout << "finite\n"; } } } #else #include using namespace std; using ll = long long; using ld = long double; #define rep(i,n) for(i=0;i<(n);i++) #define all(a) a.begin(), a.end() namespace nskr{ //nyaan氏の実装をかなり参考にした template struct modint{ int v; static int& MOD(){ static int mod = 998244353; return mod; } static int get_mod() { return MOD(); } static void set_mod(int m) { MOD() = m; } modint() :v(0){} modint(long long x) : v( (x>=0 ? x%MOD() : (x%MOD() + MOD()))){} long long val() const {return v;} modint& operator+=(const modint& x){if((v+=x.v) >= MOD()) v-=MOD(); return *this; } modint& operator-=(const modint& x){if((v-=x.v) < 0 ) v+=MOD(); return *this; } modint& operator*=(const modint& x){v = (int)(1ll * v * x.v % MOD()); return *this;} modint& operator/=(const modint& x){v = (int)(1ll * v * x.inv().val() % MOD()); return *this;} modint operator-() const {return modint(-v);} modint operator+() const {return *this;} modint operator+(const modint& x) const {return modint(*this)+=x;} modint operator-(const modint& x) const {return modint(*this)-=x;} modint operator*(const modint& x) const {return modint(*this)*=x;} modint operator/(const modint& x) const {return modint(*this)/=x;} bool operator== (const modint& x) const {return v==x.v;} bool operator!= (const modint& x) const {return v!=x.v;} friend ostream &operator<<(ostream &os, const modint &p) { return os << p.v; } friend istream &operator>>(istream &is, modint &a) { int t; is >> t; a = modint(t); return (is); } modint pow(unsigned long long n) const { modint ret(1), mul(v); while(n){ if(n&1) ret *= mul; mul *= mul; n >>=1; } return ret; } modint inv() const{ //参考: https://qiita.com/sesame0224/items/f2ac77c367f588c0d29d int a = v, b = MOD(), u = 1, w = 0; while(b){ int t = a/b; swap(a -= t*b, b); swap(u -= t*w, w); } u%=MOD(); return(u<0?u+MOD():u); } }; template struct combination{ vector fac; combination():fac({mint(1)}){} void preculc(int n){ fac.reserve(n); while(fac.size() <= n){ fac.push_back( (*fac.rbegin()) * mint(fac.size()) ); } return; } mint comb(int n, int r){ if(r>n || r<0 || n<0) return 0; if(n-r < r) r = n-r; if(fac.size() > n) return fac[n] * fac[r].inv() * fac[n-r].inv(); else{ mint ret = fac[r].inv(); for(;r--;) ret *= (n-r+1); return ret; } } }; } #endif