비밀번호 검사

어떤 회사가 온라인 시스템에 쓸 비밀번호 검사기를 만들어 달라고 요청했다. 새 사용자가 비밀번호를 입력하면 그 비밀번호가 좋은 비밀번호인지 판정해야 한다. 좋은 비밀번호는 아래 조건을 모두 만족한다.

• 길이가 9자 이상 20자 이하다. 9자와 20자도 허용한다.
• 영문 소문자가 2개 이상 들어 있다.
• 영문 대문자가 2개 이상 들어 있다.
• 숫자가 1개 이상 들어 있다.
• 특수 문자가 2개 이상 들어 있다. 비밀번호에 쓰이는 특수 문자는 : ! @ # $ % ^ & * . , ; / ? 뿐이다.
• 같은 문자가 세 번 연속으로 나오지 않는다. 대문자와 소문자는 서로 다른 문자로 보므로 aAa는 괜찮지만 aaa는 안 된다.
• 특수 문자를 모두 지우고 대소문자를 무시했을 때 남는 영숫자 문자열이 회문이 아니다. 예를 들어 &Ra^#r는 rar가 남으므로 회문이다.
• 특수 문자를 모두 지우고 대소문자를 무시했을 때 남는 영숫자 문자열에서, 순서를 지켜 문자를 골라 만든 부분 수열이 아래 단어와 같으면 안 된다. 뒤에서부터 읽은 순서도 마찬가지다. 고른 문자가 서로 붙어 있을 필요는 없다. 예를 들어 pKassWordL과 KdRrowSmsap은 둘 다 올바르지 않은 비밀번호다.
  • password
  • virginia
  • cavalier
  • code

첫째 줄에 테스트 케이스의 개수 N이 주어진다. 다음 N개 줄에 검사할 비밀번호가 한 줄에 하나씩 주어진다. 비밀번호에는 공백이 없다.

각 테스트 케이스마다 한 줄씩, 위 조건을 모두 만족하면 Valid Password를, 하나라도 어기면 Invalid Password를 출력한다.