#include <bits/stdc++.h>
#define int long long
using namespace std;
int t, n, a[1000005], s[1000005];
int check (int k) {
	int x = LLONG_MIN, y = LLONG_MAX;
	for (int i = k; i <= n; i += k) {
		x = max(abs(s[i] - s[i - k]), x);
		y = min(abs(s[i] - s[i - k]), y);
	}
	return x - y;
}
signed main (void) {
	cin >> t;
	int sum = 0;
	while (t--) {
		sum = 0;
		memset(s, 0, sizeof(s));
		cin >> n;
		int l = LLONG_MAX, r = LLONG_MIN;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			s[i] = s[i - 1] + a[i];
			l = min(l, a[i]);
			r = max(r, a[i]);
		}
		sum = max(sum, r - l);
		for (int i = 1; i <= 2 * sqrt(n); i++) {
			if (n % i == 0) {
				sum = max(sum, check(i));
				sum = max(sum, check(n / i));
			}
		}
		cout << sum << endl;
	}
	return 0;
}

void dfs(int xx,int yy){
	vis[xx][yy]=1;
	for(int i=0;i<4;i++){
		int tx=xx+dx[i],ty=yy+dy[i];
		if(tx<0||tx>n-1||ty<0||ty>m-1){
			continue;
		}
		if(mp[tx][ty]=='1'||vis[tx][ty]!=0){
			continue;
		}
		dfs(tx,ty);
	}
}
int check(int s){
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=s;i++){
		vis[x[i]][y[i]]=2;
	}
	for(int i=0;i<m;i++){
		if(mp[0][i]=='0'&&vis[0][i]==0){
			dfs(0,i);
		}
	}
	for(int i=0;i<m;i++){
		if(vis[n-1][i]==1){
			return 1;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t, n, m, q, sx, sy;
char a[505][505], b[505][505];
bool vis[505][505], flag = false;
int x[250005], y[250005], dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
struct node {
	int x, y;
};
void dfs(int x, int y) {
	if (x == n) {
		flag = true;
		return;
	}
	if (flag) return ;
	for (int i = 0; i < 4; i++) {
		int tx = dx[i] + x, ty = dy[i] + y;
		if (tx < 1 || ty < 1 || tx > n || ty > m || vis[tx][ty] || b[tx][ty] == '1') continue;
		vis[tx][ty] = true;
		dfs(tx, ty);
	}
}
bool check(int mid) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			vis[i][j] = false;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			b[i][j] = a[i][j];
		}
	}
	for (int i = 1; i <= mid; i++) b[x[i]][y[i]] = '1';
	flag = false;for (int i = 1; i <= m; i++)if (b[1][i] == '0') dfs(1, i);return flag;
}
signed main() {
	cin >> t;
	while (t--) {
		int year,cnt=0,num=0;
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> a[i][j];
				vis[i][j] = false;
			}
		}
		cin >> q;
		for (int i = 1; i <= q; i++) cin >> x[i] >> y[i], x[i]++, y[i]++;
		if (check(q)) {
			cout << -1 << endl;
			continue;
		}
		int l = 0, r = q, mid;
		while (l < r) {
			mid = l + r >> 1;
			check(mid) ? l = mid + 1 : r = mid;
		}
		cout << r << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
#define maxn 3005
#define inf 0x3f
using namespace std;
inline int read() {
	int x = 0, w = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0') {
		if (ch == '-')w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();
	return x * w;
}

struct node {
	int nxt, to;
} edge[maxn << 1];
int dis[3][maxn], head[maxn];
int s1, s2, t1, t2, tot, n, m;
queue<int> q;

inline void add(int u, int v) {
	edge[++tot].nxt = head[u];
	edge[tot].to = v;
	head[u] = tot;
}

inline void addedge(int u, int v) {
	add(u, v), add(v, u);
}

void bfs(int st, int *dis) {
	q.push(st);
	dis[st] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = head[u]; i; i = edge[i].nxt) {
			int v = edge[i].to;
			if (dis[v] > dis[u] + 1)
				dis[v] = dis[u] + 1, q.push(v);
		}
	}
}

int main(void) {
	n = read(), m = read();
	for (int i = 1; i <= m; i++) {
		int u = read(), v = read();
		addedge(u, v);
	}
	memset(dis, inf, sizeof(dis));
	s1 = read(), t1 = read(), s2 = read(), t2 = read();
	bfs(1, dis[0]), bfs(s1, dis[1]), bfs(s2, dis[2]);
	int ans = inf;
	for (int i = 1; i <= n; i++)
		if (dis[0][i] + dis[1][i] <= t1 && dis[0][i] + dis[2][i] <= t2)
			ans = min(ans, dis[0][i] + dis[1][i] + dis[2][i]);
	if (ans == inf) puts("-1");
	else printf("%d\n", m - ans);
	return 0;
}