패턴 겹침

Alice는 독서를 좋아하고 책을 많이 산다. 그녀는 책을 두 상자에 보관하며, 각 상자에는 그 상자에 보관된 모든 책의 제목과 일치하는 패턴이 표시되어 있다. 패턴은 영문 대문자와 소문자, 별표(*)만으로 이루어진다. 별표 하나는 영 개에서 네 개 사이의 문자와 일치할 수 있다. 예를 들어, 제목이 GoneGirl 및 GoneTomorrow인 책은 패턴이 Gone**인 상자에 넣을 수 있지만, 제목이 TheGoneGirl, Gonetomorrow, GoneWithTheWind인 책은 넣을 수 없다.

Alice는 두 상자 중 어느 쪽에도 보관할 수 있는 책이 존재하는지 궁금해한다. 즉, 두 상자의 패턴 모두와 일치하는 제목이 존재하는지 궁금해한다.

제한

1 ≤ T ≤ 50. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 20초. 각 패턴의 길이는 1 ≤ ≤ 200이다. 각 패턴에는 별표가 최대 5개 포함된다.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 40초. 각 패턴의 길이는 1 ≤ ≤ 2000이다.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어지며, 각 줄에는 모든 문자가 영문 대문자, 영문 소문자 또는 * 중 하나인 문자열 하나가 주어진다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 두 패턴 모두와 일치하는 문자열이 존재하면 TRUE이고, 그렇지 않으면 FALSE이다.

예제 케이스 #1에서는 제목 It이 두 패턴 모두와 일치한다. *가 문자 영 개와 일치하는 것도 가능하다는 점에 유의한다.

예제 케이스 #2에서는 제목 Shakespeare이 두 패턴 모두와 일치한다.

예제 케이스 #3에서는 두 패턴 모두와 일치하는 제목이 없다. 예를 들어, Shakespeare은 사용할 수 없는데, *peare 패턴의 시작 부분에 있는 *가 여섯 개의 문자와 일치할 수 없기 때문이다.