日常刷题

CodeForces - 1328C

A number is ternary if it contains only digits 0, 1and 2. For example, the following numbers are ternary: 1022, 11, 21, 2002.

You are given a long ternary number x. The first (leftmost) digit of x is guaranteed to be 2, the other digits of x can be 0, 1 or 2.

Let’s define the ternary XOR operation ⊙ of two ternary numbers a and b (both of length n) as a number c=a⊙b of length n, where ci=(ai+bi)%3 (where % is modulo operation). In other words, add the corresponding digits and take the remainders of the sums when divided by 3. For example, 10222⊙11021=21210.

Your task is to find such ternary numbers a and b both of length n and both without leading zeros that a⊙b=x and max(a,b) is the minimum possible.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow. The first line of the test case contains one integer n (1≤n≤5⋅104) — the length of x. The second line of the test case contains ternary number x consisting of n digits 0,1 or 2. It is guaranteed that the first digit of x is 2. It is guaranteed that the sum of n over all test cases does not exceed 5⋅104 (∑n≤5⋅104).

Output

For each test case, print the answer — two ternary integers a and b both of length n and both without leading zeros such that a⊙b=x and max(a,b) is the minimum possible. If there are several answers, you can print any.

Example

Input

4

5

22222

5

21211

1

2

9

220222021

Output

11111

11111

11000

10211

1

1

110111011

110111010

题目大致意思就是进行进制为三的不进位加法。比如2+2=2；找到两个数，使a+b=n;

不同的情况要进行不同的判定，

当前面分配的数字都相同的时候：2,分成（1,1），0分成（0,0），如何分配无所谓，但是1，分成（1,0）

如果前面分配的数字不同，即前面分配的有一位a>b,后面所有的数字都可以分给b

import java.util.Scanner;
public class c1 {
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int t=sc.nextInt();
    while(t-->0) {
      int n=sc.nextInt();
      String s=sc.next();
    char st[]= s.toCharArray();
    char pt1[]=new char[st.length];
    char pt2[]=new char[st.length];
    int flag=1;//判定
    for(int i=0;i<st.length;i++) {
    if(flag==1) {
      if(st[i]=='2') {
      pt1[i]='1';
      pt2[i]='1';
    }else if(st[i]=='1') {
      pt1[i]='1';
      pt2[i]='0';
      flag=0;
    }else if(st[i]=='0') {
      pt1[i]='0';
      pt2[i]='0';
    }
  }
    else {
      pt1[i]='0';
      pt2[i]=st[i];
    }
    }
    System.out.println(pt1);
    System.out.println(pt2);
    } 
}
}