ZERO ONE TWO

 

Steve, who is lazy and an expert of petty tricks, is annoyed of having to memorize the passwords. He may carry a memo, but it may be exposed to others. So, he thought of an idea.

 

He will create a password with the remaining numbers after removing the pairs of same numbers from a number string consisting of numbers 0~9. After removing the same number pairs, he can also remove the number pairs whose right and left numbers are the same. Following example shows the password from a number string after removing the applicable number pairs.  

[Input]

The first line of the input file provides the length of the test case. The next line contains the number character string without a space.

The character string consists of numbers between 0~9. The length of the character string N 10≤N≤100. The length of the password is smaller than the length of the character string.

[Output]

Each of 10 lines of the output file contains the answer (password) to each of 10 test cases. Each line begins with ‘#x’ followed by a space and then the answer. Here, x is the test case number.
 
[Input Example]

10 1238099084  
16 4100112380990844

...

 
[Output Example]

#1 1234
#2 4123

...
    
10 1238099084
16 4100112380990844
26 12380990844100112380990844
42 123809908444100112380990844100112380990844
55 1238099084441001123809908441001321238099084432180990844
60 123809908444100145351123809908441001321238099084432180990844
71 12380990844410013218099084441001123809908441001321238099084432180990844
99 123809908444100180990844410013211238099084410013212380990844123809908441238099084410013232180990844
82 1238099084441001410011238099084412380990844100132123809908441238099084432180990844
58 0899809812380990844100132123809908441238099084432180990844
    #include <iostream>

using namespace std;

char str[100];
int n;

void deleteChar(int i){
	int l = i - 1, r = i + 2;
	while(l >= 0 && r < n && str[l] == str[r]) l--, r++;
	l++;
	if(r != n){
		for(; r < n; r++, l++){
			str[l] = str[r];
		}
	}
	str[l] = '\0';
	n = l;
}

int checkLoop(){
	for(int i = 0; i < n - 1 ; i++){
		if(str[i] == str[i+1]) return i;
	}
	return n;
}

int main() {
	freopen("input.txt", "r", stdin);

	for(int tc = 1; tc <= 10; tc++) {
		cin >> n;
		cin >> str;
		while(true){
			if(checkLoop() == n) break;
			deleteChar(checkLoop());
		}

		// Output
		cout << "#" << tc << " " << str << endl;
	}

	return 0;
}