리스크

리스크는 세계를 무대로 한 보드 위에서 진행되는 유명한 보드 게임이다. 이 세계는 국경선으로 나뉘어진 여러 지역으로 이루어져 있고, 각각의 지역은 하나의 플레이어에게 배정된다. 모든 지역엔 각 지역을 가진 플레이어의 군대가 하나 이상 주둔해야 한다.

각 턴마다, 당신은 당신의 군대를 제자리에 두거나 인접한 자신의 영토로 보낼 수 있다. 딱히 이동할 군대가 없다면 턴을 패스하는 것도 가능하다. 각 군대는 현재 턴에 주둔한 영역에서 인접한 영역으로의 이동만이 가능하며, 이와 같은 조건 하에서라면 여러 번 군대를 이동시켜도 상관없다. 필요하다면 나누어 보낼 수도 있지만, 모든 군대를 이동시켜 영토에 주둔하는 군대가 0이 되게 할 수는 없다.

일반적으로는 적의 영토와 인접한 영역에 최대한의 군대를 보내는 전략을 사용한다. 이번 턴에 당신은 당신이 가진 영역 중 가장 취약한 영역(즉, 적국과 인접해 있으며 아군의 수가 가장 적은 영역)을 최대한 강하게 만드려고 한다. 이때, 이번 턴이 끝나면 당신의 가장 취약한 영역에 최대 몇 명의 군대가 주둔할 수 있을까?

첫 줄에 테스트 케이스의 수가 주어진다. 이 수는 100을 넘지 않는다.

각 테스트 케이스는 다음과 같이 구성되어 있다.

• 정수 n ( 1 ≤ n ≤ 100 ) : 영토의 총 수
• n개의 정수 ai ( 0 ≤ ai ≤ 100 ) : 각 지역에 주둔하고 있는 당신의 군대 수. 만일 이 값이 0이라면 적군에 의해 점령된 지역임을 의미한다.
• n개의 줄에 걸쳐 n개의 문자 'Y' 또는 'N' : i행 j열의 문자는 i번째 영토와 j번째 영토의 인접 여부를 나타낸다. 'Y' 일 경우 인접하며, 'N' 일 경우 인접하지 않는다. 항상 대칭으로 주어지며, i번째 행의 i번째 열은 항상 'N' 이다.

모든 테스트 케이스에서 당신은 적어도 하나의 영토를 갖고 있으며, 당신의 적 또한 최소한 하나의 영토를 갖고 있다. 또한, 최소한 적국과 하나의 영토는 서로 인접해 있다.

각 테스트 케이스마다 첫 줄에 가장 취약한 영역에 배치될 수 있는 최대의 군대 수를 출력한다.