A. Puzzle From the Future Codeforces Solution

A. Puzzle From the Future

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

                                                                    output

standard output 

$\mathrm{In\; the\; 2022}$ year, Mike found two binary integers a$a$ and b$b$ of length n$n$ (both of them are written only by digits 0In$0$ and 1$1$) that can have leading zeroes. In order not to forget them, he wanted to construct integer d$d$ in the following way:

• he creates an integer c$c$ as a result of bitwise summing of a$a$ and b$b$ without transferring carry, so c$c$ may have one or more 2$2$-s. For example, the result of bitwise summing of 0110$0110$ and 1101$1101$ is 1211$1211$ or the sum of 011000$011000$ and 011000$011000$ is 022000$022000$;
• after that Mike replaces equal consecutive digits in c$c$ by one digit, thus getting d$d$. In the cases above after this operation, 1211$1211$ becomes 121$121$ and 022000$022000$ becomes 020$020$ (so, d$d$ won't have equal consecutive digits).

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

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

Input

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

The first line of each test case contains the integer n$n$ (1≤n≤105$1\le n\le {10}^5$) — the length of a$a$ and b$b$.

The second line of each test case contains binary integer b$b$ of length n$n$. The integer b$b$ consists only of digits 0$0$ and 1$1$.

It is guaranteed that the total sum of n$n$ over all t$t$ test cases doesn't exceed 105${10}^5$.

Output

For each test case output one binary integer a$a$ of length n$n$. Note, that a$a$ or b$b$ may have leading zeroes but must have the same length n$n$.

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=0$b=0$ and choosing a=1$a=1$ gives d=1$d=1$ as a result.

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

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

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

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

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

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

SOLUTION:

Basically we'll check for each bits by doing it's sum with the bits of b if it hold the equality with the pervious sum bits then just put the 0 in string else keep same :)

1. #include<bits/stdc++.h>
2. using namespace std;
3. void run() {
4. int N;
5. string B;
6. cin >> N >> B;
7. string A(N, '?');
8. A[0] = '1';
9.  
10. for (int i = 1; i < N; i++) {
11. A[i] = '1';
12.  
13. if (A[i] + B[i] == A[i - 1] + B[i - 1])
14. A[i] = '0';
15. }
16.  
17. cout << A << '\n';
18. }
19.  
20. int main() {
21.  
22. int tests;
23. cin >> tests;
24.  
25. while (tests--)
26. run();
27. }

Hope this would be helpful