time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

In the 20222022 year, Mike found two binary integers aa and bb of length nn (both of them are written only by digits 00 and 11) that can have leading zeroes. In order not to forget them, he wanted to construct integer dd in the following way:

• he creates an integer cc as a result of bitwise summing of aa and bb without transferring carry, so cc may have one or more 22-s. For example, the result of bitwise summing of 01100110 and 11011101 is 12111211 or the sum of 011000011000 and 011000011000 is 022000022000;
• after that Mike replaces equal consecutive digits in cc by one digit, thus getting dd. In the cases above after this operation, 12111211 becomes 121121 and 022000022000 becomes 020020 (so, dd won't have equal consecutive digits).

Unfortunately, Mike lost integer aa before he could calculate dd himself. Now, to cheer him up, you want to find any binary integer aa of length nn such that dd will be maximum possible as integer.

Maximum possible as integer means that 102>21102>21, 012<101012<101, 021=21021=21 and so on.

Input

The first line contains a single integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

The first line of each test case contains the integer nn (1≤n≤1051≤n≤105) — the length of aa and bb.

The second line of each test case contains binary integer bb of length nn. The integer bb consists only of digits 00 and 11.

It is guaranteed that the total sum of nn over all tt test cases doesn't exceed 105105.

Output

For each test case output one binary integer aa of length nn. Note, that aa or bb may have leading zeroes but must have the same length nn.

Example

input

Copy

5
1
0
3
011
3
110
6
111000
6
001011

output

Copy

1
110
100
101101
101110

Note

In the first test case, b=0b=0 and choosing a=1a=1 gives d=1d=1 as a result.

In the second test case, b=011b=011 so:

• if you choose a=000a=000, cc will be equal to 011011, so d=01d=01;
• if you choose a=111a=111, cc will be equal to 122122, so d=12d=12;
• if you choose a=010a=010, you'll get d=021d=021.
• If you select a=110a=110, you'll get d=121d=121.

We can show that answer a=110a=110 is optimal and d=121d=121 is maximum possible.

In the third test case, b=110b=110. If you choose a=100a=100, you'll get d=210d=210 and it's the maximum possible dd.

In the fourth test case, b=111000b=111000. If you choose a=101101a=101101, you'll get d=212101d=212101 and it's maximum possible dd.

In the fifth test case, b=001011b=001011. If you choose a=101110a=101110, you'll get d=102121d=102121 and it's maximum possible dd.

解题说明：此题采用贪心算法，首先保证字符串最长，然后确保不出现连续相同的数字即可。

#include<stdio.h>
char b[100100];

int main() 
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n;
		scanf("%d", &n);
		scanf("%s", b + 1);
		int q = -1;
		for (int i = 1; i <= n; i++) 
		{
			if (b[i] - '0' + 1 != q)
			{
				printf("1");
				q = b[i] - '0' + 1;
			}
			else
			{
				printf("0");
				q = b[i] - '0';
			}
		}
		printf("\n");
	}
	return 0;
}