Problem Description

Today is the 1st anniversary of BestCoder. Soda, the contest manager, gets a string s of length n. He wants to find three nonoverlapping substrings s[l1..r1], s[l2..r2], s[l3..r3] that:

1. 1≤l1≤r1<l2≤r2<l3≤r3≤n

2. The concatenation of s[l1..r1], s[l2..r2], s[l3..r3] is "anniversary".

 

Input

There are multiple test cases. The first line of input contains an integer T (1≤T≤100), indicating the number of test cases. For each test case:

There's a line containing a string s (1≤|s|≤100) consisting of lowercase English letters.

 

Output

For each test case, output "YES" (without the quotes) if Soda can find such thress substrings, otherwise output "NO" (without the quotes).

 

Sample Input

 

Sample Output

 

Source

 

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<stdlib.h>

#define N 110

using namespace std;

int len;

char s[N], str[] = "anniversary";

bool DFS(int d, int l1, int l2)//d表示搜索的层次，l1表示从s的l1位置处开始，l2表示str从l2位置处开始，二者进行比较

{

    int i, a, b;

    if(l2 == )

        return true;//搜到str的完整序列，且之前搜索的层次不大于3

    if(d > )

        return false;//搜索的层次大于3则返回false

    for(i = l1 ; i < len ; i++)

    {

        a = i;//表示从s的a位置处开始

        b = l2;//表示从str的b位置处开始

        if(s[i] == str[l2])

        {

            while(s[a] == str[b] && a < len && b < )

            {

                a++;

                b++;

            }

            if(DFS(d + , a, b))

                return true;

        }

    }

    return false;

}

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        scanf("%s", s);

        len = strlen(s);

        if(DFS(, , ))

            printf("YES\n");

        else

            printf("NO\n");

    }

    return ;

}