A. Divisibility Problem

You are given two positive integers a and b. In one move you can increase aa by 1 (replace a with a+1). Your task is to find the minimum number of moves you need to do in order to make a divisible by b. It is possible, that you have to make 0 moves, as a is already divisible by b. 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 only line of the test case contains two integers a and b (1 ≤ a, b ≤ 109).

Output

For each test case print the answer — the minimum number of moves you need to do in order to make a divisible by b.

Example

input

5
10 4
13 9
100 13
123 456
92 46

output

2
5
4
333
0

Problem solving

题意就是给你两个整数a,b。a每次可以+1变成a+1,问a需要加多少次才可以变成b的倍数。

这道题只需要用b-a%b就行了。注意a可能本身就是b的倍数,所以最后需要再对b取模。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline void solve()
{
    ll a,b;
    cin>>a>>b;
    cout<<(b - a % b) % b<<endl;
}
int main()
{
    int T;cin>>T;
    while(T--) solve();
    return 0;
}

B. K-th Beautiful String

For the given integer n (n > 2) let’s write down all the strings of length n which contain n−2 letters ‘a’ and two letters ‘b’ in lexicographical (alphabetical) order.

Recall that the string s of length n is lexicographically less than string t of length n, if there exists such i (1 ≤ i ≤n), that s i < t i , and for any j (1 ≤ j < i) s i = t i. The lexicographic comparison of strings is implemented by the operator < in modern programming languages.

For example, if n=5 the strings are (the order does matter):

  1. aaabb
  2. aabab
  3. aabba
  4. abaab
  5. ababa
  6. abbaa
  7. baaab
  8. baaba
  9. babaa
  10. bbaaa

It is easy to show that such a list of strings will contain exactly $\frac{n⋅(n−1)}{2}$ strings.

You are given n (n > 2) and kk (1≤ k ≤ $\frac{n·(n-1)}{2}$). Print the k-th string from the list.

Input

The input contains one or more test cases.

The first line contains one integer t (1 ≤ t ≤ 104) — the number of test cases in the test. Then t test cases follow.

Each test case is written on the the separate line containing two integers n and k (3 ≤ n ≤ 105,1 ≤ k ≤ min(2⋅109, $\frac{n⋅(n−1)}{2}$).

The sum of values n over all test cases in the test doesn’t exceed 105.

Output

For each test case print the k-th string from the list of all described above strings of length n. Strings in the list are sorted lexicographically (alphabetically).

Example

input

7
5 1
5 2
5 8
5 10
3 1
3 2
20 100

output

aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa

Problem solving

题意是说给你一个n和k, 求用n-2个字符 ‘a’ 和2个字符 ‘b’ 进行全排列后字典序第k大的字符串。

因为 ‘a’ 的字典序比 ‘b’ 小,再根据样例可以看到,我们可以先找到第一个 ‘b’的位置,因为第一个 ‘b’ 的位置是有规律的,从倒数第二个开始,依次往左分别有1,2,3,4,5,6,…,i 个。所以我们可以用k依次减掉这些数,当k小于等于 i 时,就找到了第一个 ‘b’ 的位置p1。所以p1 = n - i;

然后第二个 ‘b’ 就有 n - i - 1个位置可以放。放的越靠后字典序越小。

#include<bits/stdc++.h>
using namespace std;
inline void solve()
{
    int n,k;
    cin>>n>>k;
    int i;
    for(i=1;;i++)
    {
        if(k<=i) break;
        k-=i;
    }
    int p1,p2;
    p1 = n-i;
    p2 = n-k+1;

    for(i=1; i<=n; i++)
        if(i==p1 ||i==p2) cout<<"b";
        else cout<<"a";
    cout<<endl;
}
int main()
{
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

C. Ternary XOR

A number is ternary if it contains only digits 00, 11 and 22. 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 xx can be 0, 1 or 2.

Let’s define the ternary XOR operation ⊙ of two ternary numbers aa and bb (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 aa 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 aa and bb 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

Problem solving

题意中定义了一个三进制的异或规则(对应位上的数相加余3),然后给你一个数x,让你输出两个数a,b,要保证这两个数的异或和等于x,并且这俩个数的最大值最小。即 :a XOR b = x , max(a,b)尽可能小。

我们只需要单独分析每一位上的数即可。根据上面的异或规则,我们可以得出:

  • 2 = 1 xor 1 或 0 xor 2 或 2 xor 0 (因为要保证尽可能小,所以a+b不应大于3)
  • 1 = 0 xor 1 或 1 xor 0
  • 0 = 0 xor 0

我们令a>b。从左到右依次判断x的每一位,

  • 如果还没分出大小:我们需要保证a,b尽量相同,即当x[i] = 2时,a[i]=b[i]=1;当x[i] = 0时,a[i]=b[i]=0。当x[i]=1时,a[i]=1,b[i]=0,这时无论后面怎么取值a已经大于b了;
  • 如果已经分出了大小:只需要将a后面的全都补0,b后面照抄x就行了,这样就保证了大值a尽可能小。
#include<bits/stdc++.h>
using namespace std;
inline void solve()
{
    int n;
    string s;
    cin>>n>>s;
    string a = "1",b = "1";
    int flag = 1;
    for(int i=1; i<n; i++)
    {
        if(flag)
        {
            if(s[i] == '2') a += "1",b += "1";
            if(s[i] == '0') a += "0",b += "0";
            if(s[i] == '1') a += "1",b += "0",flag = 0;
        }
        else
        {
            a += "0";
            b += s[i];
        }
    }
    cout<<a<<endl<<b<<endl;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

一个好奇的人