리스크

리스크는 세계 지도를 무대로 하는 유명한 보드 게임이다. 세계는 국경으로 나뉜 여러 지역으로 이루어지며, 각 지역은 정확히 한 명의 플레이어에게 속한다. 당신이 소유한 모든 지역에는 항상 당신의 군대가 최소 한 명 이상 주둔해 있어야 한다.

당신의 차례가 되면, 각 군대를 제자리에 두거나 인접한 자신의 지역으로 한 칸 이동시킬 수 있다. 한 군대는 이번 차례가 시작될 때 주둔해 있던 지역에서 인접한 지역으로 딱 한 번만 이동할 수 있으며, 두 칸 이상 연속으로 움직일 수는 없다. 대신 이러한 이동을 원하는 만큼 여러 군대에 대해 수행할 수 있고, 한 지역의 군대를 여러 목적지로 나누어 보낼 수도 있다. 단, 어떤 지역이든 군대를 모두 빼내어 그 지역의 주둔 군대가 0이 되게 만들 수는 없다. 이동시킬 군대가 없다면 차례를 그냥 넘겨도 된다.

적의 지역과 맞닿은 지역에 군대를 최대한 모으는 것이 일반적인 전략이다. 이번 차례에 당신은 자신이 가진 지역 중 가장 취약한 지역, 즉 적의 지역과 인접해 있으면서 주둔 군대가 가장 적은 지역을 최대한 튼튼하게 만들고자 한다. 이번 차례가 끝났을 때, 가장 취약한 지역에 주둔시킬 수 있는 군대 수의 최댓값은 얼마인가?

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 100$)가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다.

• 첫 줄에 지역의 총 개수 $n$ ($1 \le n \le 100$)이 주어진다.
• 다음 줄에 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 100$)이 주어진다. $a_i$는 $i$번째 지역에 주둔한 당신의 군대 수이며, 값이 $0$이면 그 지역은 적이 점령한 지역이다.
• 이어서 $n$개의 줄이 주어지며, 각 줄은 'Y' 또는 'N' 문자 $n$개로 이루어진다. $i$번째 줄의 $j$번째 문자가 'Y'이면 $i$번째 지역과 $j$번째 지역이 인접함을, 'N'이면 인접하지 않음을 뜻한다. 인접 관계는 항상 대칭이며, 모든 $i$에 대해 $i$번째 줄의 $i$번째 문자는 'N'이다.

모든 테스트 케이스에서 당신은 적어도 하나의 지역을 소유하고, 적도 적어도 하나의 지역을 소유하며, 당신의 지역과 적의 지역 중 인접한 쌍이 적어도 하나 존재한다.

각 테스트 케이스마다, 가장 취약한 지역(적과 인접한 당신의 지역 중 주둔 군대가 가장 적은 지역)에 주둔시킬 수 있는 군대 수의 최댓값을 한 줄에 출력한다.