PTSD

JB 왕국에는 번호가 $1, 2, \cdots, n$인 병사 $n$명이 있다. $i$번 병사의 힘 값은 $i$이다.

왕국에서 토너먼트가 열린다. 병사들은 각 병사가 정확히 한 그룹에만 속하도록 여러 그룹으로 나뉜다. 그룹에는 병사 한 명만 들어갈 수도 있다.

일부 병사는 외상 후 스트레스 장애(PTSD)를 앓고 있다. PTSD가 있는 병사는 자기 그룹에서 자신보다 힘 값이 큰 병사가 정확히 한 명일 때 불쾌해한다. 즉, 그 병사가 그룹에서 두 번째로 강한 경우이다.

왕 JB는 불쾌해하는 병사들의 힘 값의 합을 최대로 만들고자 한다. 병사들을 나누어 이 최댓값을 구하라.

첫 줄에는 테스트 케이스의 개수를 나타내는 양의 정수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에는 병사의 수를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어진다.

둘째 줄에는 길이가 $n$이고 '0'과 '1'로만 이루어진 문자열 $s$가 주어진다. $i$번째 문자는 $i$번 병사를 나타낸다. $s_i$가 '1'이면 $i$번 병사는 PTSD가 있다. 그렇지 않으면 PTSD가 없다.

모든 테스트 케이스의 $n$의 합은 $10^6$을 넘지 않는다.

각 테스트 케이스마다, 불쾌해하는 병사들의 힘 값 합의 최댓값을 한 줄에 출력한다.

첫 번째 테스트 케이스의 유효한 분할은 [1, 2], [3, 4], [5]이다. 이 분할에서는 1번 병사와 3번 병사가 불쾌해한다. [1, 2], [3, 5], [4]도 유효한 분할이다.

두 번째 테스트 케이스의 유효한 분할은 [1, 2], [3, 4], [5, 6], [7, 8]이다.

세 번째 테스트 케이스의 유효한 분할은 [1, 3], [2, 4]이다.

네 번째 테스트 케이스의 유효한 분할은 [1, 2, 3, 4]이다.