#include <stdio.h>
#include <string.h>
char input[21];
int length;
int dfs(int front, int end)//front : 앞에서 부터 찾아가는 인덱스, end : 뒤에서 부터 찾아가는 인덱스
{
if (end <= front) //앞 인덱스와 뒤 인덱스가 만나면 더이상 탐색할 필요가 없다.
{
return 1;
}
if ((input[front]!='*' && input[end]!='*') && (input[front] != input[end])) //'*'이 아니면서 두 위치가 다르면 실패
{
return 0;
}
if ((input[front] != '*' && input[end] != '*') && (input[front] == input[end])) //'*' 키워드가 아닌 상태로 두 문자가 같으면 다음 문자 비교
{
return dfs(front + 1, end - 1);
}
//키워드 중에 '*'이 있는 경우
//'*'의 길이가 0일때
//'*'의 길이가 k면서 'X'특정 문자일 때
int result = 0;
if (input[front] == '*' && input[end] == '*')// 둘다 *인 경우
{
result = dfs(front + 1, end - 1); //둘다 길이를 0으로 보고 넘김
if (result)//가능한 경우 그대로 리턴
{
return result;
}
//front를 0으로 보고 넘김
result = dfs(front + 1, end);
if (result)//가능한 경우 그대로 리턴
{
return result;
}
//end를 0으로 보고 넘김
result = dfs(front, end - 1);
if (result)//가능한 경우 그대로 리턴
{
return result;
}
//front를 길이 k의 특정 문자로 생각
for (int i = end, j=1; i > front; i--, j++)
{
if (input[i] == input[i - 1])//같은 문자인 경우
{
result = dfs(front + 1, end - j);
}
if (result)//가능한 경우 그대로 리턴
{
return result;
}
}
//end를 길이 k의 특정 문자로 생각
for (int i = front, j = 1; i < end; i++, j++)
{
if (input[i] == input[i + 1])//같은 문자인 경우
{
result = dfs(front + i, end - 1);
}
if (result)//가능한 경우 그대로 리턴
{
return result;
}
}
}
if (input[front] == '*')
{
//front를 0으로 보고 넘김
result = dfs(front + 1, end);
if (result)//가능한 경우 그대로 리턴
{
return result;
}
for (int i = end, j = 1; i > front; i--, j++)
{
if (input[i] == input[i - 1])//같은 문자인 경우
{
result = dfs(front + 1, end - j);
}
if (result)//가능한 경우 그대로 리턴
{
return result;
}
}
}
if (input[end] == '*')
{
result = dfs(front , end-1);
if (result)//가능한 경우 그대로 리턴
{
return result;
}
for (int i = front, j = 1; i < end; i++, j++)
{
if (input[i] == input[i + 1])//같은 문자인 경우
{
result = dfs(front + i, end - 1);
}
if (result)//가능한 경우 그대로 리턴
{
return result;
}
}
}
return result;
}
int main(void)
{
int t;
scanf("%d\n", &t);
for (int test_case = 1; test_case <= t; test_case++)
{
scanf("%s", input);
length = strlen(input);
int check = dfs(0, length - 1);
if (check) {
printf("#%d Exist\n", test_case);
}
else {
printf("#%d Not exist\n", test_case);
}
}
return 0;
}