D. Decrease the Sum of Digits Codeforces Round 667 (Div. 3)

You are given a positive integer n�. In one move, you can increase n� by one (i.e. make n:=n+1�:=�+1). Your task is to find the minimum number of moves you need to perform in order to make the sum of digits of n� be less than or equal to s�.

You have to answer t� independent test cases.

Input

The first line of the input contains one integer t� (1≤t≤2⋅1041≤�≤2⋅104) — the number of test cases. Then t� test cases follow.

The only line of the test case contains two integers n� and s� (1≤n≤10181≤�≤1018; 1≤s≤1621≤�≤162).

Output

For each test case, print the answer: the minimum number of moves you need to perform in order to make the sum of digits of n� be less than or equal to s�.

Example

input

5
2 1
1 1
500 4
217871987498122 10
100000000000000001 1

output

8
0
500
2128012501878
899999999999999999

题目大意：

读入两个数x,y，问使x每个位置上的数字和小于等于y至少要加多少？

 思路：

贪心，从前往后遍历，x每个位置上的数之和小于等于y，那么还不需要加数值。

但x每一位数上的和等于y时，记录x此时数字的位置，因为当后面还有数字时，那么x此时的位置也需要进位。

当x有一位数上的和大于y时，这一位数和后面的所有数都需要进位。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
 
void solve(){
	ll x=0,y,z=0,w,jl=-1;
	bool f=0;
	string s,jg=""; 
	cin >> s >> y;
	for(ll i = 0 ; i < s.size() ; i ++){
		x+=s[i]-'0';
		if(x == y && jl < 0)jl=i;
		if(x > y){
			jl != -1 ? w = jl : w = i;
			break;
		}
	}
	if(y >= x){
		cout << 0 << endl;
		return;
	}
	for(ll i = s.size()-1 ; i >= w ; i --){
		if(z == 0 && i == w && x == y)break;
		if(z == 0)jg=to_string((10-(s[i]-'0'))%10)+jg;
		else jg=to_string((10-(s[i]-'0')-1)%10)+jg;
		z+=s[i]-'0';
	}
	while(jg.size() > 1 && jg[0] == '0')jg.erase(jg.begin());//清除前导0 
	cout << jg << endl;
	return;
}
 
int main(){
	ll t=1;cin >> t;
	while(t--)solve();
	return 0;
}