#include<iostream>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<long long, int> ll_i;

#define PI 3.141592653589793238462643383279
#define mod 1000000007LL
#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define per(i, n) for(i = n - 1;i > -1;--i)
#define int(x) int x; scanf("%d",&x)
#define int2(x, y) int x, y; scanf("%d%d",&x, &y)
#define int3(x, y, z) int x, y, z; scanf("%d%d%d",&x, &y, &z)
#define int4(v, x, y, z) int v, x, y, z; scanf("%d%d%d%d", &v, &x, &y, &z)
#define int5(v, w, x, y, z) int v, w, x, y, z; scanf("%d%d%d%d%d", &v, &w, &x, &y, &z)
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define kabe puts("---------------------------")
#define kara puts("")
#define debug(x) cout << " --- " << (x) << "\n"
#define debug2(x, y) cout << " --- " << (x) << " " << (y) << "\n"
#define debug3(x, y, z) cout << " --- " << (x) << " " << (y) << " " << (z) << "\n"
#define X first
#define Y second
#define eps 0.0001
#define prid(x) printf("%.15lf\n", x)

string s[255];
int n;

int solve(bool x){
  int i, j, r, res = 0;
  if(x){
    rep(i, n)for(j = 0;j < n;){
      if(s[i][j] == '0'){ ++j; continue; }
      for(r = j + 1;r < n;++r)if(s[i][r] == '0')break;
      res = max(res, r - j);
      j = r;
    }
  }else{
    rep(i, n){
      for(j = 0;j < n - i;){
        if(s[j][j + i] == '0'){ ++j; continue; }
        for(r = j + 1;r + i < n;++r)if(s[r][r + i] == '0')break;
        res = max(res, r - j);
        j = r;
      }
      for(j = 0;j < n - i;){
        if(s[j + i][j] == '0'){ ++j; continue; }
        for(r = j + 1;r + i < n;++r)if(s[r + i][r] == '0')break;
        res = max(res, r - j);
        j = r;
      }
    }
  }
  return res;
}
void pr(void){
  int i;
  kabe;
  rep(i, n)cout << s[i] << endl;
  return;
}
signed main(void){
  int i, j;
  for(int testcase = 0;testcase >= 0;testcase++){
    scanf("%d", &n);
    if(!n)break;

    rep(i, n)cin >> s[i];

    int res = 0;
    res = solve(1);
    rep(i, n)rep(j, i)swap(s[i][j], s[j][i]);
    res = max(res, solve(1));
    rep(i, n)rep(j, i)swap(s[i][j], s[j][i]);
    res = max(res, solve(0));
    rep(i, n)rep(j, n / 2)swap(s[i][j], s[i][n - j - 1]);
    res = max(res, solve(0));
    pri(res);

//*/

//*/ break;
  }
  return 0;
}
### Prompt

Develop a solution in CPP to the problem described below:

There is a n × n grid D where each cell contains either 1 or 0.

Your task is to create a program that takes the gird data as input and computes the greatest number of consecutive 1s in either vertical, horizontal, or diagonal direction.

For example, the consecutive 1s with greatest number in the figure below is circled by the dashed-line.

<image>

The size of the grid n is an integer where 2 ≤ n ≤ 255.



Input

The input is a sequence of datasets. The end of the input is indicated by a line containing one zero. Each dataset is formatted as follows:


n
D11 D12 ... D1n
D21 D22 ... D2n
.
.
Dn1 Dn2 ... Dnn


Output

For each dataset, print the greatest number of consecutive 1s.

Example

Input

5
00011
00101
01000
10101
00010
8
11000001
10110111
01100111
01111010
11111111
01011010
10100010
10000001
2
01
00
3
000
000
000
0


Output

4
8
1
0

### Response

```cpp
#include<iostream>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<long long, int> ll_i;

#define PI 3.141592653589793238462643383279
#define mod 1000000007LL
#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define per(i, n) for(i = n - 1;i > -1;--i)
#define int(x) int x; scanf("%d",&x)
#define int2(x, y) int x, y; scanf("%d%d",&x, &y)
#define int3(x, y, z) int x, y, z; scanf("%d%d%d",&x, &y, &z)
#define int4(v, x, y, z) int v, x, y, z; scanf("%d%d%d%d", &v, &x, &y, &z)
#define int5(v, w, x, y, z) int v, w, x, y, z; scanf("%d%d%d%d%d", &v, &w, &x, &y, &z)
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define kabe puts("---------------------------")
#define kara puts("")
#define debug(x) cout << " --- " << (x) << "\n"
#define debug2(x, y) cout << " --- " << (x) << " " << (y) << "\n"
#define debug3(x, y, z) cout << " --- " << (x) << " " << (y) << " " << (z) << "\n"
#define X first
#define Y second
#define eps 0.0001
#define prid(x) printf("%.15lf\n", x)

string s[255];
int n;

int solve(bool x){
  int i, j, r, res = 0;
  if(x){
    rep(i, n)for(j = 0;j < n;){
      if(s[i][j] == '0'){ ++j; continue; }
      for(r = j + 1;r < n;++r)if(s[i][r] == '0')break;
      res = max(res, r - j);
      j = r;
    }
  }else{
    rep(i, n){
      for(j = 0;j < n - i;){
        if(s[j][j + i] == '0'){ ++j; continue; }
        for(r = j + 1;r + i < n;++r)if(s[r][r + i] == '0')break;
        res = max(res, r - j);
        j = r;
      }
      for(j = 0;j < n - i;){
        if(s[j + i][j] == '0'){ ++j; continue; }
        for(r = j + 1;r + i < n;++r)if(s[r + i][r] == '0')break;
        res = max(res, r - j);
        j = r;
      }
    }
  }
  return res;
}
void pr(void){
  int i;
  kabe;
  rep(i, n)cout << s[i] << endl;
  return;
}
signed main(void){
  int i, j;
  for(int testcase = 0;testcase >= 0;testcase++){
    scanf("%d", &n);
    if(!n)break;

    rep(i, n)cin >> s[i];

    int res = 0;
    res = solve(1);
    rep(i, n)rep(j, i)swap(s[i][j], s[j][i]);
    res = max(res, solve(1));
    rep(i, n)rep(j, i)swap(s[i][j], s[j][i]);
    res = max(res, solve(0));
    rep(i, n)rep(j, n / 2)swap(s[i][j], s[i][n - j - 1]);
    res = max(res, solve(0));
    pri(res);

//*/

//*/ break;
  }
  return 0;
}
```