사이 나쁜 여왕들

체스에서 여왕은 가로, 세로, 대각선 방향으로 거리 제한 없이 움직이며 그 경로에 있는 말을 공격한다.

사이 나쁜 여왕 퀴즈는 8x8 체스판에 여왕 여덟 개를 놓되 어떤 두 여왕도 서로 공격하지 못하게 놓는 퀴즈다. 두 여왕이 같은 행에 있거나 같은 열에 있거나 같은 대각선 위에 있으면 서로 공격한다.

체스판 하나와 그 위의 여왕 배치가 주어진다. 이 배치가 퀴즈의 올바른 해법인지 판정하라. 판 위에 여왕이 정확히 여덟 개 있고 그중 어떤 두 여왕도 서로 공격하지 않을 때만 올바른 해법이다.

체스판이 여덟 줄로 주어진다. 각 줄은 문자 여덟 개다.

각 문자는 . 또는 *이며, .은 빈 칸을, *은 여왕이 놓인 칸을 나타낸다.

올바른 해법이면 valid를, 올바르지 않으면 invalid를 한 줄에 출력한다.