#include "Anna.h"
#include <iostream>
#include <cstring>

typedef long long ll;

using namespace std;

namespace
{
	const int MAXN = 5e5 + 10;
	int n;
	string pat[4] = {"2202102012001101000", "2202102011012000", "220210201101200", "22021020120011000"};

	inline void Trans(string &s)
	{
		for (int i = 0; i < s.size(); i++)
			if (s[i] == '0') s[i] = 'R';
			else if (s[i] == '1') s[i] = 'G';
			else if (s[i] == '2') s[i] = 'B';
			else if (s[i] == 'R') s[i] = '0';
			else if (s[i] == 'G') s[i] = '1';
			else s[i] = '2';
	}
}

pair <string, int> anna(int N, string S)
{
	n = N;
	if (n < 28)
	{
		Trans(S);
		for (int i = 0; i < n; i++)
			if (S[i] == '2') S[i] = '0';
			else S[i]++;
		Trans(S);
		return make_pair(S, n);
	}
	Trans(S);
	int p = 0, ed = (n - 1) / 9 + 1;
	while (S.size() < ed * 9) S.push_back('0');
	string ret = "";
	for (int _ = 0; _ < ed; _++)
	{
		for (int u = 0; u < 4; u++)
		{
			int tar = pat[u][_ % pat[u].size()] - '0'; bool flag = 1;
			for (int i = 0; i < 3 && flag; i++)
				if (i != S[p] - '0')
					for (int j = 0; j < 3; j++)
						if (j != S[p + 1] - '0' && (j - i + 3) % 3 == tar)
						{ ret.push_back(i + '0'), ret.push_back(j + '0'), flag = 0; break; }
			p += 2;
		}
		for (int i = 0; i < 3; i++)
			if (i != S[p] - '0' && i != ret.back() - '0') { ret.push_back(i + '0'); break; }
		p++;
	}
	ret.resize(n), Trans(ret);
	return {ret, min(n, 28)};
}

#include "Bruno.h"
#include <iostream>
#include <cstring>
#include <map>

typedef long long ll;

using namespace std;

namespace
{
	const int MAXN = 5e5 + 10;
	int n;
	string pat[4] = {"2202102012001101000", "2202102011012000", "220210201101200", "22021020120011000"};

	inline void Trans(string &s)
	{
		for (int i = 0; i < s.size(); i++)
			if (s[i] == '0') s[i] = 'R';
			else if (s[i] == '1') s[i] = 'G';
			else if (s[i] == '2') s[i] = 'B';
			else if (s[i] == 'R') s[i] = '0';
			else if (s[i] == 'G') s[i] = '1';
			else s[i] = '2';
	}

	map <string, int> pos[4];
	map <tuple <int, int, int, int>, int> idx;
	int d[40];
}

void init(int N, int l)
{
	n = N;
	if (n < 28) return;
	for (int i = 0; i < 4; i++)
	{
		string cur = pat[i] + pat[i];
		for (int j = 0; j < pat[i].size(); j++)
			pos[i][cur.substr(j, 3)] = j;
	}
	int ed = (n - 1) / 9 + 1;
	for (int i = 0; i < ed; i++) idx[make_tuple(i % pat[0].size(), i % pat[1].size(), i % pat[2].size(), i % pat[3].size())] = i;
}

int bruno(string str)
{
	if (str.size() < 28) return 1;
	Trans(str);
	for (int i = 1; i < str.size(); i++) d[i - 1] = (str[i] - str[i - 1] + 3) % 3;
	bool avl[9] = {0};
	for (int i = 0; i < 27; i++) avl[i % 9] |= (d[i] == 0);
	int zr[15], top = 0;
	for (int i = 0; i < 9; i++)
		if (!avl[i]) zr[++top] = i;
	int stt = 0;
	if (top == 1) stt = zr[1];
	else
	{
		stt = zr[top];
		for (int i = top - 1; ~i; i--)
			if ((zr[i + 1] - zr[i]) & 1) { stt = zr[i]; break; }
	}
	int tmp[4];
	for (int i = 2; i <= 8; i += 2)
	{
		int s = (stt + i) % 9; string cur = "";
		for (int j = 0; j < 3; j++)
			cur.push_back(d[s + j * 9] + '0');
		int id = i / 2 - 1, p = pos[id][cur];
		if (s > stt) p = (p - 1 + (int)pat[id].size()) % pat[id].size();
		tmp[id] = p;
	}
	int ans = idx[make_tuple(tmp[0], tmp[1], tmp[2], tmp[3])];
	return (ans + 1) * 9 - stt - 1;
}