# 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

#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

#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

• 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[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;
}