Problem: You are given a positive integer n. In one move, you can increase n by one (i.e. make n := n + 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 ⋅ 10^4) — 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 ≤ 10^{18}; 1 ≤ s ≤ 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

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

public class D667 {
    static int [] a;
    static int n;
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int t = sc.nextInt();
        while (t-- > 0) {
            String num = sc.next(); int s = sc.nextInt();
            long x = Long.parseLong(num);
            n = num.length();
            a = new int[n];
            for (int i = 0; i < n; i++) a[i] = num.charAt(i) - '0';
            int sum = 0;
            for (int i = 0; i < n; i++) sum += a[i];
            if (sum <= s) {
                out.println(0);
                continue;
            }
            long ans = Long.MAX_VALUE;
            int [] suf = new int[n];
            suf[n - 1] = a[n - 1];
            for (int i = n - 2; i >= 0; i--) {
                suf[i] = suf[i + 1] + a[i];
            }
            long [] pow = new long[19];
            pow[0] = 1;
            for (int i = 1; i <= 18; i++) pow[i] = pow[i - 1] * 10;
            for (int i = 0; i < n; i++) {
                for (int dig = 0; dig < 10; dig++) {
                    if (dig <= a[i]) continue;
                    long res = x / pow[n - i - 1];
                    res += (dig - a[i]);
                    res *= pow[n - 1 - i];
                    if (res == Long.MAX_VALUE) continue;
                    int temp = sum + dig - a[i] - (i == n - 1 ? 0 : suf[i + 1]);
                    if (temp <= s) {
                        ans = Math.min(res - x, ans);
                    }
                }
            }
            ans = Math.min(pow[n] - x, ans);
            out.println(ans);
        }
        out.close();
    }


    static long carry(int index, int dig) {
        if (a[index] >= dig) return Long.MAX_VALUE;
        int [] ret = new int[n];
        ret[index] = dig;
        for (int i = index - 1; i >= 0; i--) {
            ret[i] = a[i];
        }
        long res = 0;
        for (int i = 0; i < n; i++) {
            res += ret[i];
            if (i != n - 1) res = res * 10;
        }
        return res;
    }


    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }


    }

}