using namespace std;
using ll = long long;
using vi = vector<int>;
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vi t(n);
        for (auto &ti : t)
            cin >> ti;
        int changes = 0;
        for (int i = 0; i < n; ++i)
            if (t[i] != t[(i - 1 + n) % n])
                ++changes;
        int color;
        if (changes % 2 == 0)
        {
            cout << (changes == 0 ? 1 : 2) << endl;
            color = 0;
            for (int i = 0; i < n; ++i)
            {
                cout << color + 1 << " ";
                if (t[i] != t[(i + 1 + n) % n])
                    color = 1 - color;
            }
            cout << endl;
        }
        else
        {
            if (changes == n)
            {
                cout << 3 << endl;
                color = 0;
                for (int i = 0; i < n; ++i)
                {
                    cout << color + 1 << " ";
                    if (i == n - 2)
                        color = 2;
                    else if (t[i] != t[(i + 1 + n) % n])
                        color = 1 - color;
                }
                cout << endl;
            }
            else
            {
                int start = 0;
                while (t[(start + n) % n] != t[(start - 1 + n) % n])
                    start = (start + 1 + n) % n;
                while (t[(start + n) % n] == t[(start + 1 + n) % n])
                    start = (start + 1 + n) % n;
                vi ans(n);
                cout << 2 << endl;
                color = 0;
                for (int i = 0; i < n; ++i)
                {
                    ans[(start + i) % n] = color + 1;
                    if (t[(start + i) % n] != t[(start + i + 1 + n) % n])
                        color = 1 - color;
                }
                for (auto x : ans)
                    cout << x << " ";
                cout << endl;
            }
        }
    }
    return 0;
}

using namespace std;
int main(void)
{
    int t, n, x, y;
    bool bigger;
    string s, a, b;
    cin >> t;
    while (t--)
    {
        cin >> n >> s;
        bigger = false;
        for (int i = 0; i < n; ++i)
        {
            if (not bigger)
            {
                y = (s[i] - '0') / 2;
                x = (s[i] - '0') - y;
                a.push_back(x + '0');
                b.push_back(y + '0');
                if (x > y)
                    bigger = true;
            }
            else
            {
                a.push_back('0');
                b.push_back(s[i]);
            }
        }
        cout << a << endl << b << endl;
        a.clear();
        b.clear();
    }
    return 0;
}

using namespace std;
using ll = long long;
int binary_search(int low, int high, int target)
{
    auto p = [&](ll x) { return ((x * (x + 1)) / 2) >= (ll)target; };
    while (low < high)
    {
        int mid = low + (high - low + 1) / 2;
        if (p((ll)mid))
            high = mid - 1;
        else
            low = mid;
    }
    if (p((ll)low))
        return 0;
    return low;
}
int main(void)
{
    int t, n, k;
    cin >> t;
    while (t--)
    {
        cin >> n >> k;
        ll b1, b2;
        b1 = (ll)binary_search(0, n, k) + 1;
        b2 = b1 - (((b1 * (b1 + 1)) / 2) - k) - 1;
        for (int i = 0; i < n; ++i)
        {
            if (i == (n - 1 - b1) or (i == n - 1 - b2))
                cout << 'b';
            else
                cout << 'a';
        }
        cout << endl;
    }
    return 0;
}

using namespace std;
int main(void)
{
    int t, a, b, mod;
    cin >> t;
    while (t--)
    {
        cin >> a >> b;
        mod = a % b;
        cout << (b - mod) % b << endl;
    }
}

using namespace std;
int n;
string s;
int solve(void)
{
    int ans, open_br, l;
    ans = open_br = 0;
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == '(')
        {
            open_br += 1;
            if (open_br == 0)
                ans += i - l + 1;
        }
        else
        {
            open_br -= 1;
            if (open_br == -1)
                l = i;
        }
    }
    if (open_br != 0)
        return -1;
    return ans;
}
int main(void)
{
    cin >> n >> s;
    cout << solve() << endl;
    return 0;
}

using namespace std;
bool r[110];
bool b[110];
int n;
int main(void)
{
    int win = 0, loss = 0, ans;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> r[i];
    for (int i = 0; i < n; ++i)
        cin >> b[i];
    for (int i = 0; i < n; ++i)
    {
        if (r[i] and not b[i])
            ++win;
        if (not r[i] and b[i])
            ++loss;
    }
    if (win > 0)
        ans = (int)ceil((loss + 1.0) / win);
    else
        ans = -1;
    cout << ans << endl;
}

using namespace std;
int n;
char s[5010];
string rev(int k)
{
    string ans(n, ' ');
    for (int i = 0; i < (n - k + 1); ++i)
        ans[i] = s[k - 1 + i];
    if ((n - k + 1) % 2 == 0)
        for (int i = n - k + 1; i < n; ++i)
            ans[i] = s[i - (n - k + 1)];
    else
        for (int i = n - 1; i >= n - k + 1; --i)
            ans[i] = s[n - i - 1];
    return ans;
}
void solve(void)
{
    string ans(s);
    int mink = 1;
    for (int k = 1; k <= n; ++k)
    {
        string cur = rev(k);
        if (cur < ans)
        {
            ans = cur;
            mink = k;
        }
    }
    cout << ans << endl << mink << endl;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> s;
        solve();
    }
}

using namespace std;
using ll = long long;
ll n, m;
ll a[1010];
ll sum;
ll solve(void)
{
    sum = accumulate(a, a + n, 0);
    ll a0 = min(sum, m);
    return a0;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        cout << solve() << endl;
    }
    return 0;
}

using namespace std;
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        int a, b, p;
        string s;
        cin >> a >> b >> p;
        cin >> s;
        int length = s.size();
        char pchar = s[length - 1];
        int size_travel = 1;
        int ctrav;
        int i;
        int ans = length - 1;
        for (i = length - 2; i >= 0; i--)
        {
            while (i >= 0 and s[i] == pchar)
            {
                ++size_travel;
                --i;
            }
            ctrav = s[i + 1] == 'A' ? a : b;
            if (i < 0)
                break;
            if (i + 1 == length - 1)
                ctrav = 0;
            pchar = s[i];
            if (p - ctrav < 0)
                break;
            p -= ctrav;
            ans = i + 1;
        }
        if (i == -1)
        {
            ctrav = s[i + 1] == 'A' ? a : b;
            if (p - ctrav >= 0)
                ans = i + 1;
        }
        cout << ans + 1 << endl;
    }
    return 0;
}

using namespace std;
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        int a, b, x, y;
        cin >> a >> b >> x >> y;
        int ans = max({x * b, a * y, (a - x - 1) * b, a * (b - y - 1)});
        cout << ans << endl;
    }
    return 0;
}