1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <algorithm>
using namespace std;

void zdrowie(int tab[], int n, int &x, int &y)
{
	int aktX=-1, aktY=n;
	int max=0, aktMax=0;
	bool hbdyz = false;
	for (int k = n - 1; k >= 0; k--)
	{
		if (tab[k] == 1 || tab[k]==2)
		{
			aktMax = 0;
			aktY = k; //zakres DO kończy się na ZARAŻONYM po prawej
		}
		else
		{
			aktX = k; //zakres OD zaczyna się na NIEZARAŻONYM po lewej
			aktMax++;
		}
		if (aktMax > max)
		{
			if (aktY == 2)
				for(int s=aktY-1;s>=0;s--)
					if (tab[s] == 1)
					{
						hbdyz = true;
						break;
					}
			if (hbdyz)
				max = aktMax, y = aktY, x = aktX;
		}
		else if (aktMax == max && aktX == 0)
		{
			if (aktY == 2)
				for (int s = aktY - 1; s >= 0; s--)
					if (tab[s] == 1)
					{
						hbdyz = true;
						break;
					}
			if (hbdyz)
				y = aktY, x = aktX;
		}
		if (y == n && tab[x - 1] == 2)
			max = 0;
		hbdyz = false;
	}
	y--; //zakres DO kończy sią na NIEZARAŻONYM po prawej
}

void szczepienie(int tab[], int n, int x, int y)
{
	if (x == 0 || tab[x - 1] == 2)
		tab[y] = 2;
	else if (y == n || tab[y + 1] == 2)
		tab[x] = 2;
}

void noc(int tab[], int n)
{
	for (int k = 1; k < n - 1; k++)
		if (tab[k] == 1)
		{
			if (tab[k - 1] == 0)
				tab[k - 1] = 1;
			if (tab[k + 1] == 0)
				tab[k + 1] = 1;
		}
	if (tab[0] == 1 && tab[1] == 0)
		tab[1] = 1;
	if (n > 1)
		if (tab[n - 1] == 1 && tab[n - 2] == 0)
			tab[n - 2] = 1;
}

bool koniec(int tab[], int n)
{
	for (int k = 1; k < n; k++)
		if (tab[k] == 1 && (tab[k - 1] == 0 || tab[k + 1] == 0))
			return false;
	if (tab[0] == 1 && tab[1] == 0)
		return false;
	return true;
}

int wynik(int tab[], int n)
{
	int wyjscie = 0;
	for (int k = 0; k < n; k++)
		if (tab[k] == 1)
			wyjscie++;
	return wyjscie;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie();
	cout.tie();

	int t, n, x, y;
	string panstwo;
	cin >> t;

	for (int i = 0; i < t; i++)
	{
		cin >> n >> panstwo;
		x = 0, y = n - 1;
		int* a = new int[n+1];
		for (int k = 0; k < n; k++)
			a[k] = panstwo[k] - 48;
		a[n] = 2;
		while (!koniec(a, n))
		{
			for (int k = 0; k < n; k++)
				cout << a[k];
			cout << '\n';
			zdrowie(a, n, x, y);
			szczepienie(a, n, x, y);
			noc(a, n);
		}
		cout << wynik(a, n) << '\n';
		for (int k = 0; k < n; k++)
			cout << a[k];
	}
}