Poetry is a form of literature that uses aesthetic and rhythmic qualities of language. There are many famous poets in the contemporary era. It is said that a few ACM-ICPC contestants can even write poetic code. Some poems has a strict rhyme scheme like "ABABA" or "ABABCAB". For example, "niconiconi" is composed of a rhyme scheme "ABABA" with A = "ni" and B = "co".

More technically, we call a poem pretty if it can be decomposed into one of the following rhyme scheme: "ABABA" or "ABABCAB". The symbol A, B and C are different continuous non-empty substrings of the poem. By the way, punctuation characters should be ignored when considering the rhyme scheme.

You are given a line of poem, please determine whether it is pretty or not.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

There is a line of poem S (1 <= length(S) <= 50). S will only contains alphabet characters or punctuation characters.

Output

For each test case, output "Yes" if the poem is pretty, or "No" if not.

Sample Input

3
niconiconi~
pettan,pettan,tsurupettan
wafuwafu

Sample Output

Yes
Yes
No

题意：给出一个长度不超过50的字符串，判断它是不是pretty串。pretty串的定义如下：如果一个串可以写成ABABA或者ABABCAB的形式，且A、B、C两两不相等，那么这个串就是pretty串。

分析：因为长度不超过50，所以可以直接枚举A、B的长度，然后暴力求解。比赛时我枚举的是AB整体的长度，不知道为什么一直WA。取子串时，可以用substr取代循环。

#include<iostream>
#include<string>
using namespace std;

bool is_pretty1(string s)
{
    if(s.length() < 5) return false;
    for(int lenA = 1; lenA <= (s.length() - 2) / 3; lenA++) {
        string A = s.substr(0, lenA);
        for(int lenB = 1; lenA * 3 + lenB * 2 <= s.length(); lenB++) {
            if(lenA * 3 + lenB * 2 != s.length()) continue;
            string B = s.substr(lenA, lenB);
            if(A != B) {
                string AA = s.substr(lenA + lenB, lenA);
                string BB = s.substr(lenA * 2 + lenB, lenB);
                string AAA = s.substr(lenA * 2 + lenB * 2, lenA);
                if(A == AA && A == AAA && B == BB)
                    return true;
            }
        }
    }
    return false;
}

bool is_pretty2(string s)
{
    if(s.length() < 7) return false;
    for(int lenA = 1; lenA <= (s.length() - 4) / 3; lenA++) {
        string A = s.substr(0, lenA);
        for(int lenB = 1; 3 * lenA + 3 * lenB < s.length(); lenB++) {
            string B = s.substr(lenA, lenB);
            if(A != B) {
                int lenC = s.length() - 3 * lenA - 3 * lenB;
                string AA = s.substr(lenA + lenB, lenA);
                string BB = s.substr(lenA * 2 + lenB, lenB);
                string C = s.substr(lenA * 2 + lenB * 2, lenC);
                string AAA = s.substr(lenA * 2 + lenB * 2 + lenC, lenA);
                string BBB = s.substr(lenA * 3 + lenB * 2 + lenC, lenB);
                if(A == AA && A == AAA && B == BB && B == BBB && A != C && B != C)
                    return true;
            }
        }
    }
    return false;
}

bool is_pretty(string s)
{
    return is_pretty1(s) || is_pretty2(s);
}

int main()
{
    int T;
    string tmp;
    cin >> T;
    while(T--) {
        cin >> tmp;
        string s = "";
        for(int i = 0; i < tmp.length(); i++)
            if(isalpha(tmp[i]))
                s += tmp[i];
        if(is_pretty(s)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

zoj 3818 Pretty Poem（暴力处理字符串）2014年牡丹江赛区网络赛