B. Максимальная подстрока
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бинарной строкой называется строка, состоящая только из символов 0 и 1. Вам дана бинарная строка $$$s$$$.

Для некоторой непустой подстроки$$$^\dagger$$$ $$$t$$$ строки $$$s$$$, состоящей из $$$x$$$ символов 0 и $$$y$$$ символов 1, определим её стоимость как:

  • $$$x \cdot y$$$, если $$$x > 0$$$ и $$$y > 0$$$;
  • $$$x^2$$$, если $$$x > 0$$$ и $$$y = 0$$$;
  • $$$y^2$$$, если $$$x = 0$$$ и $$$y > 0$$$.

Вам дана бинарная строка $$$s$$$ длины $$$n$$$, найдите максимальную стоимость среди всех её непустых подстрок.

$$$^\dagger$$$ Строка $$$a$$$ является подстрокой $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину строки $$$s$$$.

Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длины $$$n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — максимальную стоимость среди всех подстрок.

Пример
Входные данные
6
5
11100
7
1100110
6
011110
7
1001010
4
1000
1
0
Выходные данные
9
12
16
12
9
1
Примечание

В первом наборе входных данных мы можем взять подстроку $$$111$$$. Она содержит $$$3$$$ символа 1 и $$$0$$$ символов 0. Таким образом, $$$a = 3$$$, $$$b = 0$$$, и её стоимость равна $$$3^2 = 9$$$.

Во втором наборе входных данных мы можем взять всё строку. Она содержит $$$4$$$ символа 1 и $$$3$$$ символа 0. Таким образом, $$$a = 4$$$, $$$b = 3$$$, и её стоимость равна $$$4 \cdot 3 = 12$$$.

В третьем наборе входных данных мы можем взять подстроку $$$1111$$$, и её стоимость равна $$$4^2 = 16$$$.

В четвёртом наборе входных данных мы можем взять всю строку. Её стоимость равна $$$4 \cdot 3 = 12$$$.

В пятом наборе входных данных мы можем взять подстроку $$$000$$$. Её стоимость равна $$$3 \cdot 3 = 9$$$.

В шестом наборе входных данных мы можем взять только подстроку $$$0$$$. Её стоимость равна $$$1 \cdot 1 = 1$$$.