A binary string is a string consisting only of the characters 0 and 1. You are given a binary string $s$.

For some non-empty substring$^\dagger$ $t$ of string $s$ containing $x$ characters 0 and $y$ characters 1, define its cost as:

$x \cdot y$, if $x > 0$ and $y > 0$;

$x^2$, if $x > 0$ and $y = 0$;

$y^2$, if $x = 0$ and $y > 0$.

Given a binary string $s$ of length $n$, find the maximum cost across all its non-empty substrings.

$^\dagger$ A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.


-----Input-----

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$.

The second line of each test case contains a binary string $s$ of length $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print a single integer — the maximum cost across all substrings.


-----Examples-----

Input
6
5
11100
7
1100110
6
011110
7
1001010
4
1000
1
0
Output
9
12
16
12
9
1


-----Note-----

In the first test case, we can take a substring $111$. It contains $3$ characters 1 and $0$ characters 0. So $a = 3$, $b = 0$ and its cost is $3^2 = 9$.

In the second test case, we can take the whole string. It contains $4$ characters 1 and $3$ characters 0. So $a = 4$, $b = 3$ and its cost is $4 \cdot 3 = 12$.

In the third test case, we can can take a substring $1111$ and its cost is $4^2 = 16$.

In the fourth test case, we can take the whole string and cost is $4 \cdot 3 = 12$.

In the fifth test case, we can take a substring $000$ and its cost is $3 \cdot 3 = 9$.

In the sixth test case, we can only take the substring $0$ and its cost is $1 \cdot 1 = 1$.

Source: codeforces | Difficulty: EASY
Tags: Complete search

Implementation

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline
out = []
t = int(input())
for _ in range(t):
	input()
	s = input().strip()
	poss = []
	z = o = tz = to = 0
	for c in s:
		if c == '0':
			tz += 1
			z += 1
			o = 0
			poss.append(z * z)
		else:
			to += 1
			o += 1
			z = 0
			poss.append(o * o)
	poss.append(tz * to)
	out.append(max(poss))
print('\n'.join(map(str, out)))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	a = s.count('1')
	m = a * (n - a)
	d = 1
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			d += 1
		else:
			m = max(m, d * d)
			d = 1
	m = max(m, d * d)
	print(m)


def max(a, b):
	if a > b:
		return a
	return b

def longestitem(l, x):
	if len(l) == 0:
		return 0
	m = 0
	while x * (m + 1) in l:
		m += 1
	return m

def calc(s):
	zeros = s.count('0')
	ones = s.count('1')
	if zeros > ones:
		return max(longestitem(s, '0') ** 2, zeros * ones)
	if ones > zeros:
		return max(longestitem(s, '1') ** 2, zeros * ones)
	return zeros * ones
l = []
for _ in range(int(input())):
	input()
	l.append(calc(input()))
print('\n'.join(map(str, l)))


def solve(s, n, ans):
	total_zero = 0
	total_one = 0
	zero = 0
	one = 0
	max_count = 0
	for i in s:
		if i == '0':
			max_count = max(max_count, one)
			one = 0
			zero += 1
			total_zero += 1
		else:
			max_count = max(max_count, zero)
			zero = 0
			one += 1
			total_one += 1
	max_count = max(max_count, zero, one)
	max_val = max_count * max_count
	max_val = max(max_val, total_zero * total_one)
	ans.append(max_val)

def main():
	t = int(input())
	ans = []
	for i in range(t):
		n = int(input())
		s = input()
		solve(s, n, ans)
	print('\n'.join(map(str, ans)))
main()


from sys import stdin, stdout

def inp():
	return int(stdin.readline())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())

def main():
	for i in range(inp()):
		n = inp()
		s = stdin.readline()
		c = s.count('0')
		one = n - c
		ans = one * c
		i = 0
		while i < n:
			ini = i
			while i < n and s[i] == s[ini]:
				i += 1
			ans = max(ans, (i - ini) ** 2)
		print(ans)
main()


for s in [*open(0)][2::2]:
	ans = max(s.count('0') * s.count('1'), 1)
	st = 1
	s = s.strip()
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			st += 1
		else:
			st = 1
		ans = max(ans, st * st)
	print(ans)


results = []
for _ in range(int(input())):
	n = int(input())
	s = input()
	a = s.count('1')
	b = n - a
	m = a * b
	c = s[0]
	d = 1
	for i in range(1, n):
		if c == s[i]:
			d += 1
		else:
			m = max(m, d * d)
			c = s[i]
			d = 1
	m = max(m, d * d)
	results.append(m)
print('\n'.join(map(str, results)))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
test_cases = inp()
inp_arr = []
for i in range(test_cases):
	num = inp()
	s = input()
	inp_arr.append(s)

def findResult(s):
	c_zero = 0
	c_one = 0
	max_lk = 0
	pre = ''
	count_lk = 0
	for i in range(len(s)):
		num = s[i]
		if num == pre:
			count_lk += 1
		else:
			max_lk = max(count_lk, max_lk)
			pre = num
			count_lk = 1
		if num == '0':
			c_zero += 1
		elif num == '1':
			c_one += 1
	result = c_zero * c_one
	return max(result, max_lk * max_lk)
result = [findResult(cheeses) for cheeses in inp_arr]
for m in result:
	print(m)


nums = []
t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = a.count('0')
	d = len(a) - b
	count = b * d
	e = a[0]
	count1 = 1
	for k in range(1, len(a)):
		if e == a[k]:
			count1 += 1
		else:
			count = max(count, count1 * count1)
			e = a[k]
			count1 = 1
	count = max(count, count1 * count1)
	nums.append(count)
print('\n'.join(map(str, nums)))


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	n = int(input())
	a = input().strip()
	x = 0
	y = 0
	mx = 0
	my = 0
	c = 0
	f = 0
	for i in a:
		if i == '0':
			x += 1
			c += 1
			y = 0
			mx = max(mx, x)
		else:
			y += 1
			my = max(my, y)
			f += 1
			x = 0
	print(max(c * f, max(mx * mx, my * my)))
	t -= 1


results = []
t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	x = a.count('0')
	y = n - x
	res = x * y
	cur = a[0]
	cnt = 1
	for i in range(1, n):
		if cur == a[i]:
			cnt += 1
		else:
			res = max(res, cnt * cnt)
			cur = a[i]
			cnt = 1
	res = max(res, cnt * cnt)
	results.append(res)
print('\n'.join(map(str, results)))


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	n = int(input())
	k = input().strip()
	c1 = 0
	c0 = 0
	a = 0
	b = 0
	max1 = 0
	max0 = 0
	for i in k:
		if i == '1':
			c1 += 1
			a += 1
			max1 = max(a, max1)
			b = 0
		else:
			b += 1
			max0 = max(b, max0)
			a = 0
	print(max((n - c1) * c1, max1 ** 2, max0 ** 2))
	t -= 1


import sys
input = sys.stdin.readline

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	n = readInt()
	s = readStr()
	ans = cnt = prev = 0
	cnt += int(s[0])
	for i in range(1, n):
		if s[i] != s[i - 1]:
			ans = max(ans, (i - prev) ** 2)
			prev = i
		cnt += int(s[i])
	ans = max(ans, (n - prev) ** 2)
	return max(ans, cnt * (n - cnt))
for _ in range(int(input())):
	print(solve())


import sys
input = lambda : sys.stdin.readline().strip()

def getMax1(arr, n):
	count = 0
	result = 0
	for i in range(0, n):
		if arr[i] == '0':
			count = 0
		else:
			count += 1
			result = max(result, count)
	return result

def getMax0(array, m):
	count = 0
	result = 0
	for i in range(len(array)):
		if array[i] == '1':
			count = 0
		else:
			count += 1
			result = max(result, count)
	return result
t = int(input())
for i in range(t):
	tc = int(input())
	inp = input()
	if len(set(inp)) == 1:
		print(len(inp) ** 2)
	else:
		x = getMax1(inp, len(inp))
		y = getMax0(inp, len(inp))
		a = inp.count('0')
		b = inp.count('1')
		print(max(x ** 2, y ** 2, a * b))


import sys
input = sys.stdin.readline
for jj in range(int(input())):
	n = int(input())
	a = input()
	kk = a.count('1')
	ans = kk * (n - kk)
	a = a + '2'
	t = 0
	ck = a[0]
	m = 0
	for i in a:
		if i == ck:
			t += 1
		else:
			m = max(m, t)
			t = 1
			ck = i
	print(max(ans, m * m))


from itertools import *
for s in [*open(0)][2::2]:
	(x, y) = map(s.count, '01')
	print(max([x * y] + [len([*g]) ** 2 for (k, g) in groupby(s)]))


from sys import stdin

def cte(l, n):
	c_0 = 0
	c_1 = 0
	subs = []
	for i in range(n):
		actual = l[i]
		if actual == '0':
			c_0 += 1
			if c_1 != 0:
				subs.append(c_1)
				c_1 = 0
		else:
			c_1 += 1
			if c_0 != 0:
				subs.append(c_0)
				c_0 = 0
	if c_1 != 0 or c_0 != 0:
		subs.append(max(c_1, c_0))
	return max(subs)

def main():
	cases = int(stdin.readline().strip())
	for c in range(cases):
		n = int(stdin.readline().strip())
		st = list(stdin.readline().strip())
		(a, b) = (st.count('1'), st.count('0'))
		print(max(cte(st, n) ** 2, a * b))
main()


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(sys.stdin.readline())
	a = sys.stdin.readline().strip()
	k = 1
	xx = 1
	for j in range(1, n):
		if a[j - 1] == a[j]:
			k += 1
		else:
			k = 1
		xx = max(xx, k)
	x = a.count('1')
	y = a.count('0')
	print(max(x * y, xx ** 2))


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	n = int(input())
	k = input().strip()
	count1 = 0
	count0 = 0
	a = 0
	b = 0
	maxcount1 = 0
	maxcount0 = 0
	for i in k:
		if i == '1':
			count1 += 1
			a += 1
			maxcount1 = max(a, maxcount1)
			b = 0
		else:
			b += 1
			maxcount0 = max(b, maxcount0)
			a = 0
	print(max((n - count1) * count1, maxcount1 ** 2, maxcount0 ** 2))
	t -= 1


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(max1, ct1, count1) = (0, 0, 0)
	(max0, count0, ct0) = (0, 0, 0)
	for k in s:
		if k == '0':
			ct0 += 1
			max0 = max(max0, ct0)
			ct1 = 0
			count0 += 1
		if k == '1':
			ct1 += 1
			max1 = max(max1, ct1)
			ct0 = 0
			count1 += 1
	print(max(max1 ** 2, max0 ** 2, count1 * count0))


import sys
sys.setrecursionlimit(10 ** 9)
input = lambda : sys.stdin.readline().strip()
from collections import defaultdict, deque
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	x1 = s.count('1')
	res1 = x1 * (n - x1)
	x2 = 1
	tx2 = 1
	i = 0
	while i < n - 1:
		tx2 = 0
		while i + 1 < n and s[i] == s[i + 1]:
			tx2 += 1
			i += 1
			x2 = max(x2, tx2 + 1)
		i += 1
	print(max(res1, x2 * x2))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	string = input()
	(cur1, cur2) = (0, 0)
	(mx1, mx2) = (0, 0)
	for i in range(n):
		if string[i] == '1':
			cur1 += 1
			mx1 = max(mx1, cur1)
			cur2 = 0
		elif string[i] == '0':
			cur2 += 1
			mx2 = max(cur2, mx2)
			cur1 = 0
	print(max(string.count('0') * string.count('1'), mx1 * mx1, mx2 * mx2))


import math
import sys
input = lambda : sys.stdin.readline().strip()
for i in range(int(input())):
	a = int(input())
	b = input()

	def Substring(s):
		(ans, temp) = (1, 1)
		for i in range(1, len(s)):
			if s[i] == s[i - 1]:
				temp += 1
			else:
				ans = max(ans, temp)
				temp = 1
		ans = max(ans, temp)
		return ans
	print(max(Substring(b) ** 2, b.count('0') * b.count('1')))


for i in [*open(0)][2::2]:
	n = len(i)
	g = i[0]
	ans = 0
	z = 1
	e = 0
	o = 0
	e += g == '0'
	o += g == '1'
	for j in range(1, n):
		if i[j] == g:
			z += 1
		else:
			ans = max(ans, z * z)
			z = 1
			g = i[j]
		e += g == '0'
		o += g == '1'
	ans = max(ans, z * z)
	ans = max(ans, e * o)
	print(ans)


T = int(input())
res = list()
for _ in range(T):
	n = int(input())
	s = input()
	(x, y) = (s.count('0'), s.count('1'))
	ans = x * y
	i = 0
	while i < len(s):
		j = i
		while i + 1 < len(s) and s[i + 1] == s[j]:
			i += 1
		ans = max(ans, (i - j + 1) * (i - j + 1))
		i += 1
	res.append(ans)
print('\n'.join(list(map(str, res))))


import sys

def input():
	return sys.stdin.readline()

def print(x):
	sys.stdout.write(f'{x}\n')
for _ in range(int(input())):
	n = int(input())
	s = input()
	(n0, n1, ans, c, l) = (0, 0, 1, 1, 1)
	for (i, e) in enumerate(s):
		if i and e == s[i - 1]:
			c += 1
		else:
			l = max(l, c)
			c = 1
		n0 += s[i] == '0'
	print(max(l * l, max(c * c, n0 * (n - n0))))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	lst = list(input()[:-1])
	(max_zero, max_one, mx_zero, mx_one) = (0, 0, 0, 0)
	for i in lst:
		if not int(i):
			mx_zero += 1
			max_zero = max(max_zero, mx_zero)
			mx_one = 0
		else:
			mx_one += 1
			max_one = max(max_one, mx_one)
			mx_zero = 0
	print(max(lst.count('0') * lst.count('1'), max_one ** 2, max_zero ** 2))


t = int(input())
iota = []
for i in range(t):
	n = int(input())
	s = input()
	(a, b) = (0, 0)
	(l, r) = (0, 0)
	(mxl, mxr) = (0, 0)
	for j in range(n):
		if s[j] == '0':
			a += 1
			if r > 0:
				mxr = max(mxr, r)
				r = 0
			l += 1
		else:
			b += 1
			if l > 0:
				mxl = max(mxl, l)
				l = 0
			r += 1
	mxl = max(mxl, l)
	mxr = max(mxr, r)
	res = max([mxl ** 2, mxr ** 2, a * b])
	iota.append(res)
print('\n'.join([str(k) for k in iota]))


from typing import Sequence

def begin(n: int, nums: Sequence):
	maxNum = 0
	currOne = 0
	currZero = 0
	one = 0
	zero = 0
	for i in range(len(nums)):
		if nums[i] == '0':
			zero += 1
			currOne = 0
			currZero += 1
			maxNum = max(maxNum, currZero)
		else:
			one += 1
			currZero = 0
			currOne += 1
			maxNum = max(maxNum, currOne)
	res = max(one * zero, maxNum * maxNum)
	return res
caseNum = int(input())
allnums = []
for i in range(0, caseNum):
	n = int(input())
	allnums.append(input())
result = [begin(n, cheeses) for cheeses in allnums]
for item in result:
	print(item)


fl = 'input.txt'
import sys
import math
flh = sys.stdin
test_cases = int(flh.readline())
res = []
for case in range(test_cases):
	n = int(flh.readline())
	s = flh.readline().strip()
	summ = sum([int(i) for i in s])
	a1 = summ * (len(s) - summ)
	count = 0
	max0 = 0
	for i in range(len(s)):
		if count == 0:
			count += 1
		elif s[i] == s[i - 1]:
			count += 1
		else:
			max0 = max(max0, count)
			count = 1
	if count > 0:
		max0 = max(max0, count)
	print(max(a1, max0 * max0))


from collections import Counter
import sys

def main():
	input = sys.stdin.readline
	t = int(input())
	for _ in range(t):
		n = int(input())
		counter = dict()
		counter['0'] = 0
		counter['1'] = 0
		nums = input()
		maxOnes = 0
		maxZeros = 0
		countZeros = 0
		countOnes = 0
		for i in range(n):
			counter[nums[i]] += 1
			if nums[i] == '0':
				countZeros += 1
				countOnes = 0
			else:
				countOnes += 1
				countZeros = 0
			maxZeros = max(maxZeros, countZeros)
			maxOnes = max(maxOnes, countOnes)
		print(max(counter['0'] * counter['1'], maxZeros ** 2, maxOnes ** 2))
main()


import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	s = input()
	a = 0
	b = 0
	c = 0
	x = 1
	for i in range(n):
		if i != 0:
			if s[i] == s[i - 1]:
				c += 1
			else:
				x = max(x, (c + 1) * (c + 1))
				c = 0
		a += s[i] == '0'
		b += s[i] == '1'
	x = max(x, (c + 1) * (c + 1))
	print(max(a * b, x))


import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	s = input()
	zx = len(s.replace('0', ''))
	zx = zx * (n - zx)
	print(max(len(max(list(s.split('0')))) ** 2, zx, len(max(list(s.split('1')))) ** 2))


import sys

def input():
	return sys.stdin.readline().strip()
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	x = 0
	y = 0
	c = 0
	d = 0
	m = []
	n = []
	for j in s:
		if j == '0':
			x += 1
			if y != 0:
				n.append(y)
				y = 0
			c += 1
		else:
			y += 1
			if x != 0:
				m.append(x)
				x = 0
			d += 1
		m.append(x)
		n.append(y)
	a = max(m)
	b = max(n)
	e = c * d
	print(max(a * a, b * b, e))


n = int(input())
ans = []
for _ in range(n):
	m = int(input())
	s = input()
	cnt = 1
	res = 1
	(c0, c1) = (1, 0)
	for i in range(1, m):
		if s[i] == s[i - 1]:
			cnt += 1
		else:
			cnt = 1
		res = max(res, cnt)
		if s[i] == s[0]:
			c0 += 1
		else:
			c1 += 1
	ans.append(max(res ** 2, c0 * c1))
for a in ans:
	print(a)


import sys
import math
FILE = False
if FILE:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def get_int():
	return int(sys.stdin.readline())

def get_string():
	return sys.stdin.readline().strip()

def write_int(n):
	return sys.stdout.write(str(n) + '\n')

def write_list(list):
	sys.stdout.write(' '.join(map(str, list)) + '\n')

def compute_cost(x, y):
	if x == 0:
		return y * y
	if y == 0:
		return x * x
	return x * y
test_cases = get_int()
for test in range(test_cases):
	num1 = 0
	num0 = 0
	result = 0
	remove = 0
	n = get_int()
	max_cost = math.inf
	input = sys.stdin.readline().strip()
	num1 = sum([int(i) for i in input])
	num0 = len(input) - num1
	if num1 == num0:
		print(num1 * num0)
	else:
		result = compute_cost(num1, num0)
		if num1 > num0:
			find = '1'
		else:
			find = '0'
		l = 0
		r = 0
		nums0 = 0
		while r < n:
			if input[r] == find:
				nums0 += 1
				result = max(result, nums0 * nums0)
			else:
				nums0 = 0
				l = r + 1
			r += 1
		print(result)


k = int(input())
result = []
for i in range(k):
	op = int(input())
	f = input()
	most1 = 0
	cnt1 = 0
	most0 = 0
	cnt0 = 0
	yek = 0
	for i in f:
		if i == '1':
			cnt0 = 0
			yek += 1
			cnt1 += 1
			if cnt1 >= most1:
				most1 = cnt1
		else:
			cnt1 = 0
			cnt0 += 1
			if cnt0 >= most0:
				most0 = cnt0
	result.append(max(max(most0 ** 2, most1 ** 2), (op - yek) * yek))
for i in result:
	print(i)


def value_of_str(str):
	x = str.count('0')
	y = str.count('1')
	if x > 0 and y > 0:
		return x * y
	if x > 0:
		return x * x
	return y * y
turns = int(input())
result = []
for _ in range(turns):
	values = []
	n = int(input())
	str = input()
	num_of_0 = 1
	str0 = '0'
	while str0 in str:
		num_of_0 += 1
		str0 = '0' * num_of_0
	num_of_1 = 1
	str1 = '1'
	while str1 in str:
		num_of_1 += 1
		str1 = '1' * num_of_1
	num_of_0 -= 1
	num_of_1 -= 1
	result.append(max(value_of_str(str), num_of_0 * num_of_0, num_of_1 * num_of_1))
for res in result:
	print(res)


n = int(input())
ans = []
for k in range(n):
	a = int(input())
	st = input()
	i = 0
	i1 = 0
	maxi = 0
	o = 0
	o1 = 0
	maxo = 0
	for j in range(a):
		if st[j] == '1':
			i = i + 1
			i1 = i1 + 1
			if j == a - 1 or st[j + 1] == '0':
				maxi = max(i, maxi)
				i = 0
		else:
			o = o + 1
			o1 = o1 + 1
			if j == a - 1 or st[j + 1] == '1':
				maxo = max(maxo, o)
				o = 0
	a = maxo * maxo
	b = maxi * maxi
	c = o1 * i1
	ans.append(max(a, b, c))
print(*ans, sep='\n')


import math
import re
import sys
from turtle import st
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def main():
	t = inp()
	res = []
	for i in range(t):
		n = inp()
		bin = input()
		num0 = 0
		num1 = 0
		for idx in range(n):
			if bin[idx] == '0':
				num0 += 1
			if bin[idx] == '1':
				num1 += 1
		num0_con = 0
		num1_con = 0
		max_num0_con = 0
		max_num1_con = 0
		for idx in range(n):
			if bin[idx] == '0':
				num0_con += 1
			if bin[idx] == '1' or idx == n - 1:
				max_num0_con = max(max_num0_con, num0_con)
				num0_con = 0
		for idx in range(n):
			if bin[idx] == '1':
				num1_con += 1
			if bin[idx] == '0' or idx == n - 1:
				max_num1_con = max(max_num1_con, num1_con)
				num1_con = 0
		if num0 == 0:
			res.append(num1 * num1)
			continue
		if num1 == 0:
			res.append(num0 * num0)
			continue
		res.append(max([num0 * num1, max_num0_con * max_num0_con, max_num1_con * max_num1_con]))
	for r in res:
		print(r)
main()


def Kolvo10(strok):
	n = len(strok)
	i = 0
	K0 = 0
	K1 = 1
	while i < n:
		k0 = 0
		k1 = 0
		while strok[i] == '0':
			k0 += 1
			i += 1
			if i == len(strok):
				break
		if k0 > K0:
			K0 = k0
		if i == len(strok):
			break
		while strok[i] == '1':
			k1 += 1
			i += 1
			if i == len(strok):
				break
		if k1 > K1:
			K1 = k1
		if i == len(strok):
			break
	return max(K0 * K0, K1 * K1)
t = int(input())
ans = []
for i in range(t):
	n = int(input())
	strok = input()
	x = 0
	y = 0
	for j in range(n):
		if strok[j] == '0':
			x += 1
		else:
			y += 1
	ans.append(max(Kolvo10(strok), x * y))
for elem in ans:
	print(elem)


import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().strip()))
	x = sum(l)
	y = n - x
	res = x * y
	col_0 = 0
	col_1 = 0
	ans_col = 0
	for i in range(n):
		if l[i] == 1:
			col_1 += 1
			col_0 = 0
		else:
			col_1 = 0
			col_0 += 1
		ans_col = max(col_1, col_0, ans_col)
	if res >= ans_col ** 2:
		print(res)
	else:
		print(ans_col ** 2)


def solve(size, s):
	c_0 = s.count('0')
	c_1 = s.count('1')
	maxi = -1
	if c_0 != 0 and c_1 != 0:
		maxi = c_0 * c_1
	elif c_1 == 0:
		maxi = c_0 ** 2
	else:
		maxi = c_1 ** 2
	max_consq0 = 0
	max_consq1 = 0
	prev_char = s[0]
	count = 1
	for i in range(1, size):
		if s[i] == prev_char:
			count += 1
		else:
			if prev_char == '0':
				if count > max_consq0:
					max_consq0 = count
			elif count > max_consq1:
				max_consq1 = count
			prev_char = s[i]
			count = 1
	if prev_char == '0':
		if count > max_consq0:
			max_consq0 = count
	if prev_char == '1':
		if count > max_consq1:
			max_consq1 = count
	if max((max_consq0 ** 2, max_consq1 ** 2)) > maxi:
		maxi = max((max_consq0 ** 2, max_consq1 ** 2))
	print(maxi)
no_testcase = int(input())
problems = []
for i in range(no_testcase):
	problems.append((int(input()), input()))
for each in problems:
	solve(each[0], each[1])


import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	x = int(input())
	s = input()
	a = len(sorted(list(map(str, s.split('0'))))[-1])
	a = max(a, len(sorted(list(map(str, s.split('1'))))[-1]))
	c = s.count('0')
	print(max(a ** 2, c * (x - c)))


n = int(input())
l = []
for i in range(n):
	a = int(input())
	k = input()
	x = k.count('0')
	y = k.count('1')
	max1 = 1
	max0 = 1
	um = 0
	num = 0
	for i in range(a):
		if k[i] == '1':
			um += 1
			num = 0
		else:
			num += 1
			um = 0
		if um > max1:
			max1 = um
		if num > max0:
			max0 = num
	l.append(max(max1 ** 2, max0 ** 2, x * y))
for i in range(n):
	print(l[i], end='\n')


t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	s = str(input())
	maxm = i = p = 0
	while i < n:
		cnt = 0
		while i < n and s[i] == '0':
			cnt += 1
			i += 1
			p += 1
		maxm = max(maxm, cnt ** 2)
		cnt = 0
		while i < n and s[i] == '1':
			cnt += 1
			i += 1
		maxm = max(maxm, cnt ** 2)
	maxm = max(maxm, p * (n - p))
	ans.append(maxm)
for i in ans:
	print(i)


t = int(input())
out = []
for i in range(t):
	n = int(input())
	st = input()
	x2 = 0
	y2 = 0
	x = st.count('0')
	y = st.count('1')
	len0 = 0
	len1 = 0
	xy = x * y
	for k in range(n):
		if st[k] == '0':
			len1 = 0
			len0 += 1
			x2 = max(x2, len0)
		else:
			len0 = 0
			len1 += 1
			y2 = max(y2, len1)
	x2 = x2 ** 2
	y2 = y2 ** 2
	out.append(max(x2, y2, xy))
for i in out:
	print(i)


a = int(input())
sp = []
k = 0
for i in range(a):
	b = int(input())
	c = input()
	a1 = 0
	k1 = 0
	k0 = 0
	a0 = 0
	h = 0
	pok = 0
	sty = []
	for j in c:
		if j == '1':
			k1 += 1
		else:
			k0 += 1
	for j in range(len(c) - 1):
		if c[j] == '1':
			a1 += 1
		if c[j] == '1' and c[j + 1] == '0':
			sty.append(a1)
			a1 = 0
		if c[j] == '0':
			a0 += 1
		if c[j] == '0' and c[j + 1] == '1':
			sty.append(a0)
			a0 = 0
		pok += 1
	if c[b - 1] == '1' and a1 >= a0:
		sty.append(a1 + 1)
	elif c[b - 1] == '0' and a0 >= a1:
		sty.append(a0 + 1)
	else:
		sty.append(max(a1, a0))
		sty.append(1)
	sp.append(max(max(sty) ** 2, k1 * k0))
for i in sp:
	print(i)


t = int(input())
dict = {}
r1 = []
result = []
for i in range(t):
	n = int(input())
	ar = [int(x) for x in input()]
	for j in ar:
		if j not in dict:
			dict[j] = 1
		else:
			dict[j] += 1
	c = 1
	for j in range(1, n):
		if ar[j] == ar[j - 1]:
			c += 1
		else:
			r1.append(c)
			c = 1
	r1.append(c)
	if max(r1) ** 2 > dict.get(0, 0) * dict.get(1, 0):
		result.append(max(r1) ** 2)
	else:
		result.append(dict[0] * dict[1])
	r1.clear()
	dict.clear()
for i in range(t):
	print(result[i])


def solve():
	t = int(input())
	while t:
		t -= 1
		N = int(input())
		s = input()
		zero = 0
		one = 0
		prev = s[0]
		count = 0
		(zeros, ones) = (0, 0)
		for c in s:
			if c == '0':
				zeros += 1
			else:
				ones += 1
			if prev == c:
				count += 1
			else:
				if prev == '0':
					if zero <= count:
						zero = count
				if prev == '1':
					if one <= count:
						one = count
				count = 1
				prev = c
		if prev == '0':
			if zero <= count:
				zero = count
		if prev == '1':
			if one <= count:
				one = count
		res = max(zero * zero, zeros * ones, one * one)
		print(res)
solve()


import os, sys
from io import BytesIO, IOBase
from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if n == 1:
		print(1)
	elif n == 2:
		if s[0] == s[1]:
			print(4)
		else:
			print(1)
	elif n == 3:
		if s[1] == s[0] == s[2]:
			print(9)
		elif s[1] == s[0] or s[1] == s[2]:
			print(4)
		else:
			print(2)
	else:
		count = 1
		curnt_cnt = 1
		prev = s[0]
		for i in range(1, n):
			if s[i] == prev:
				curnt_cnt += 1
			else:
				count = max(curnt_cnt, count)
				curnt_cnt = 1
				prev = s[i]
		count = max(curnt_cnt, count)
		cnt = Counter(s)
		print(max(count ** 2, cnt['0'] * cnt['1']))


test_cases = int(input())
for _ in range(test_cases):
	input()
	s = input()
	if len(s) == 1:
		print(1)
		continue
	(x, y) = (0, 0)
	(max_g1, max_g0) = (0, 0)
	(temp1, temp0) = (0, 0)
	for i in s:
		if i == '1':
			temp1 += 1
			y += 1
			temp0 = 0
			if temp1 >= max_g1:
				max_g1 = temp1
		else:
			temp0 += 1
			x += 1
			temp1 = 0
			if temp0 >= max_g0:
				max_g0 = temp0
	if x * y >= max_g1 ** 2 and x * y >= max_g0 ** 2:
		print(x * y)
	elif max_g1 ** 2 >= x * y and max_g1 ** 2 >= max_g0 ** 2:
		print(max_g1 ** 2)
	else:
		print(max_g0 ** 2)


def start_codeforces():
	a = int(input())
	while a != 0:
		a -= 1
		a2 = 0
		c = 0
		d = 0
		san = int(input())
		text = input()
		count = 1
		if text[0] == '1':
			c += 1
		else:
			d += 1
		for i in range(1, san):
			if text[i] == text[i - 1]:
				count += 1
			else:
				a2 = max(a2, count)
				count = 1
			if text[i] == '1':
				c += 1
			else:
				d += 1
		a2 = max(a2, count)
		if a2 * a2 > c * d:
			print(a2 ** 2)
		else:
			print(c * d)
start_codeforces()


for _ in range(int(input())):
	n = int(input())
	s = input()
	if n == 1:
		print(1)
	else:
		a = s.count('1')
		b = s.count('0')
		ans = a * b
		g = 1
		temp = 1
		for i in range(n - 1):
			if s[i] == s[i + 1]:
				temp += 1
			else:
				g = max(g, temp)
				temp = 1
		g = max(g, temp)
		g = g * g
		ans = max(g, ans)
		print(ans)


def longest(s):
	maximum = count = 0
	current = ''
	for c in s:
		if c == current:
			count += 1
		else:
			count = 1
			current = c
		if count > maximum:
			maximum = count
	return maximum

def solve(s, length):
	try:
		no_mix = longest(s)
		z = s.count('0')
		mix = z * (int(length) - z)
		r = no_mix * no_mix
		if mix > r:
			print(mix)
		else:
			print(r)
	except Exception as e:
		print(e.with_traceback())
		print(length * length)
for i in range(int(input())):
	length = int(input())
	s = input()
	solve(s, length)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	oc = a.count('1')
	zc = a.count('0')
	if oc == 0:
		print(zc ** 2)
		continue
	if zc == 0:
		print(oc ** 2)
		continue
	best = 1
	mc = 1
	for i in range(len(a) - 1):
		if a[i + 1] == a[i]:
			mc += 1
			if mc > best:
				best = mc
		else:
			if mc > best:
				best = mc
			mc = 1
			if best >= len(a) - (i + 1):
				break
	print(max(best ** 2, oc * zc))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	z = s.count('0')
	if z == n:
		print(z * z)
		continue
	o = len(s) - z
	if o == n:
		print(o * o)
		continue
	m = z * o
	c = math.ceil(math.sqrt(m))
	if '1' * c in s:
		while '1' * (c + 1) in s:
			c += 1
		if c < n // 2:
			while '0' * (c + 1) in s:
				c += 1
		print(c * c)
	elif '0' * c in s:
		while '0' * (c + 1) in s:
			c += 1
		if c < n // 2:
			while '1' * (c + 1) in s:
				c += 1
		print(c * c)
	else:
		print(m)


for _ in range(int(input())):
	n = int(input())
	a = input()
	if n == 1:
		print('1')
		continue
	(b, d) = (0, 0)
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			d += 1
		else:
			b = max(b, d)
			d = 0
	b = max(b, d)
	b += 1
	x = a.count('0')
	y = a.count('1')
	print(max(x * y, b * b))


for _ in range(int(input())):
	n = int(input())
	s = input()
	if n == 1:
		print('1')
		continue
	a = s.count('1')
	b = s.count('0')
	m = a * b
	maxx = 0
	d = 1
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			d += 1
		else:
			maxx = max(maxx, d)
			d = 1
	maxx = max(maxx, d)
	print(max(m, maxx * maxx))


for i in range(int(input())):
	input()
	s = input()
	x = s.count('0')
	y = s.count('1')
	if x == 0:
		print(y ** 2)
	elif y == 0:
		print(x ** 2)
	else:
		count = 0
		a = '0'
		b = '1'
		while s.count(a) > 0 or s.count(b) > 0:
			count += 1
			a += '0'
			b += '1'
		print(max(x * y, count ** 2))


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	x = s.count('0')
	y = s.count('1')
	ans = x * y
	count = 1
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			count += 1
		else:
			m = count * count
			if m > ans:
				ans = m
			count = 1
	m = count * count
	if m > ans:
		ans = m
	print(ans)


def longest(l, r):
	k = 1
	u = 0
	for i in range(len(l) - 1):
		if l[i] == l[i + 1]:
			k = k + 1
		else:
			if k > u:
				u = k
			k = 1
	if k > u:
		u = k
	if u * u > r:
		return u * u
	else:
		return r
for _ in range(int(input())):
	n = int(input())
	l = list(input())
	r = l.count('0') * l.count('1')
	print(longest(l, r))


k = int(input())
for z in range(k):
	trash = int(input())
	number = str(input())
	ee = len(number)
	if ee == 0:
		print(0)
	elif ee == 1:
		print(1)
	else:
		coun = 0
		checker = '0'
		counter = 0
		maxcounter = 0
		for x in number:
			if x == '1':
				coun += 1
			if x == checker:
				counter += 1
			elif x != checker:
				maxcounter = counter if maxcounter < counter else maxcounter
				counter = 1
				checker = x
		maxcounter = counter if maxcounter < counter else maxcounter
		if maxcounter ** 2 > coun * (len(number) - coun):
			print(maxcounter ** 2)
		else:
			print(coun * (len(number) - coun))


t = int(input())
for ii in range(t):
	n = int(input())
	s = input()
	ans = 0
	x = s.count('0')
	y = s.count('1')
	if x == 0:
		ans = y * y
	elif y == 0:
		ans = x * x
	else:
		ans = x * y
	z = 1
	a = 0
	for i in range(1, n):
		if s[i] != s[i - 1]:
			a = z * z
			if a > ans:
				ans = a
			z = 1
		else:
			z += 1
	a = z * z
	if a > ans:
		ans = a
	print(ans)


a = int(input())
while a:
	a -= 1
	d = int(input())
	c = input()
	tmp1 = 0
	max1 = 0
	a1 = 0
	flag = c[0]
	for i in c:
		if i == '1':
			a1 += 1
		if flag == i:
			tmp1 += 1
		else:
			max1 = max(tmp1, max1)
			tmp1 = 1
			flag = i
	max1 = max(tmp1, max1)
	a0 = d - a1
	print(max([a1 * a0, max1 * max1]))


def b():
	t = int(input())
	for _ in range(t):
		_ = int(input())
		s = input()
		max_ones = max_zeros = 0
		ones_in_row = zeros_in_row = 0
		ones = zeros = 0
		for char in s:
			if char == '1':
				ones += 1
				ones_in_row += 1
				zeros_in_row = 0
				max_ones = max(max_ones, ones_in_row)
			elif char == '0':
				zeros += 1
				zeros_in_row += 1
				ones_in_row = 0
				max_zeros = max(max_zeros, zeros_in_row)
		max_ones = max(max_ones, ones_in_row)
		max_zeros = max(max_zeros, zeros_in_row)
		print(max(max_ones * max_ones, max_zeros * max_zeros, ones * zeros))
b()


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 1
	gp = 1
	for i in range(1, len(s)):
		if s[i - 1] == s[i]:
			gp += 1
			ans = max(ans, gp * gp)
		else:
			gp = 1
	ans = max(ans, s.count('0') * s.count('1'))
	print(ans)


def main():
	tc = int(input())
	for i in range(tc):
		l = int(input())
		st = input()
		cnt = 1
		ans = 1
		for i in range(l - 1):
			if st[i] == st[i + 1]:
				cnt += 1
			else:
				cnt = 1
			ans = max(cnt, ans)
		(one, zero) = (0, 0)
		for i in range(l):
			if st[i] == '1':
				one += 1
			else:
				zero += 1
		tmp = one * zero % 100000000000
		tmp2 = ans * ans % 100000000000
		if tmp2 > tmp:
			print(tmp2)
		else:
			print(tmp)
main()


t = int(input())
for i in range(t):
	l = int(input())
	s = str(input())
	c = 0
	c_max = 0
	temp = str(s[0])
	z = 0
	o = 0
	for a in s:
		if a == temp:
			c = c + 1
		else:
			c = 1
		if a == '0':
			z = z + 1
		else:
			o = o + 1
		temp = a
		if c_max < c:
			c_max = c
	if c_max * c_max >= z * o:
		print(c_max * c_max)
	else:
		print(z * o)


t = int(input())
for _ in range(t):
	(n, s) = (int(input()), input())
	(res, cur) = (0, 1)
	for i in range(1, n):
		if s[i] == s[i - 1]:
			cur += 1
		else:
			(res, cur) = (max(res, cur), 1)
	res = max(res * res, cur * cur, (z := s.count('0')) * (n - z))
	print(res)


for i in range(int(input())):
	n = int(input())
	s = input()
	ans = max(s.count('0') * s.count('1'), 1)
	c = 1
	for j in range(1, n):
		if s[j] == s[j - 1]:
			c += 1
		else:
			c = 1
		ans = max(ans, c * c)
	print(ans)


n = int(input())
for i in range(n):
	t = int(input())
	str = input()
	length = 0
	L = 0
	if len(str) == 1:
		print(1)
	else:
		for j in range(t - 1):
			if str[j] != str[j + 1]:
				length += 1
				L = max(L, length)
				length = 0
			else:
				length += 1
		if length != 0:
			length += 1
			L = max(L, length)
		L2 = str.count('0') * str.count('1')
		print(max(L2, L ** 2))


def solve(case_no: int):
	n = int(input())
	string = input()
	(max_1s, max_0s) = (0, 0)
	(left, right) = (0, 0)
	(ones, zeros) = (0, 0)
	for i in string:
		if i == '0':
			right += 1
			zeros += 1
			max_1s = max(max_1s, left)
			left = 0
		else:
			left += 1
			ones += 1
			max_0s = max(max_0s, right)
			right = 0
	(max_1s, max_0s) = (max(max_1s, left), max(max_0s, right))
	print(max(ones * zeros, max_0s * max_0s, max_1s * max_1s))
test_case = int(input())
for _ in range(test_case):
	solve(_ + 1)