CF1474A Puzzle From the Future

In the $ 2022 $ year, Mike found two binary integers $ a $ and $ b $ of length $ n $ (both of them are written only by digits $ 0 $ and $ 1 $ ) that can have leading zeroes. In order not to forget them, he wanted to construct integer $ d $ in the following way: - he creates an integer $ c $ as a result of bitwise summing of $ a $ and $ b $ without transferring carry, so $ c $ may have one or more $ 2 $ -s. For example, the result of bitwise summing of $ 0110 $ and $ 1101 $ is $ 1211 $ or the sum of $ 011000 $ and $ 011000 $ is $ 022000 $ ; - after that Mike replaces equal consecutive digits in $ c $ by one digit, thus getting $ d $ . In the cases above after this operation, $ 1211 $ becomes $ 121 $ and $ 022000 $ becomes $ 020 $ (so, $ d $ won't have equal consecutive digits). Unfortunately, Mike lost integer $ a $ before he could calculate $ d $ himself. Now, to cheer him up, you want to find any binary integer $ a $ of length $ n $ such that $ d $ will be maximum possible as integer. Maximum possible as integer means that $ 102 > 21 $ , $ 012 < 101 $ , $ 021 = 21 $ and so on.

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The first line of each test case contains the integer $ n $ ( $ 1 \leq n \leq 10^5 $ ) — the length of $ a $ and $ b $ . The second line of each test case contains binary integer $ b $ of length $ n $ . The integer $ b $ consists only of digits $ 0 $ and $ 1 $ . It is guaranteed that the total sum of $ n $ over all $ t $ test cases doesn't exceed $ 10^5 $ .

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

In the first test case, $ b = 0 $ and choosing $ a = 1 $ gives $ d = 1 $ as a result. In the second test case, $ b = 011 $ so: - if you choose $ a = 000 $ , $ c $ will be equal to $ 011 $ , so $ d = 01 $ ; - if you choose $ a = 111 $ , $ c $ will be equal to $ 122 $ , so $ d = 12 $ ; - if you choose $ a = 010 $ , you'll get $ d = 021 $ . - If you select $ a = 110 $ , you'll get $ d = 121 $ . We can show that answer $ a = 110 $ is optimal and $ d = 121 $ is maximum possible.In the third test case, $ b = 110 $ . If you choose $ a = 100 $ , you'll get $ d = 210 $ and it's the maximum possible $ d $ . In the fourth test case, $ b = 111000 $ . If you choose $ a = 101101 $ , you'll get $ d = 212101 $ and it's maximum possible $ d $ . In the fifth test case, $ b = 001011 $ . If you choose $ a = 101110 $ , you'll get $ d = 102121 $ and it's maximum possible $ d $ .