You are given two integers l and r, l≤ r. Find the largest possible value of a mod b over all pairs (a, b) of integers for which r≥ a ≥ b ≥ l.

As a reminder, a mod b is a remainder we get when dividing a by b. For example, 26 mod 8 = 2.

Input

Each test contains multiple test cases.

The first line contains one positive integer t (1≤ t≤ 10^4), denoting the number of test cases. Description of the test cases follows.

The only line of each test case contains two integers l, r (1≤ l ≤ r ≤ 10^9).

Output

For every test case, output the largest possible value of a mod b over all pairs (a, b) of integers for which r≥ a ≥ b ≥ l.

Example

Input


4
1 1
999999999 1000000000
8 26
1 999999999


Output


0
1
12
499999999

Note

In the first test case, the only allowed pair is (a, b) = (1, 1), for which a mod b = 1 mod 1 = 0.

In the second test case, the optimal choice is pair (a, b) = (1000000000, 999999999), for which a mod b = 1.
import java.io.*;
import java.math.BigInteger;
import java.util.*;

import static java.lang.Math.*;

public class B {
    static boolean[] isPrime;
    static int N = (int) 1e5;
    static ArrayList<Integer> list;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        sieve();
        build();
        int t = in.nextInt();
        for (int tt = 0; tt < t; tt++) {
            HashSet<Character> set = new HashSet<>();
            int k = in.nextInt();
            char[] s = in.next().toCharArray();
            for (char temp : s) set.add(temp);
            boolean good = false;
            for (int i = 0; i < s.length; i++) {
                set.add(s[i]);
                if (set.contains('4')) {
                    pw.println(1);
                    pw.println(4);
                    good = true;
                   break;
                }
                if (set.contains('6')) {
                    pw.println(1);
                    pw.println(6);
                    good = true;
                    break;
                }
                if (set.contains('8')) {
                    pw.println(1);
                    pw.println(8);
                    good = true;
                    break;
                }
                if (set.contains('9')) {
                    pw.println(1);
                    pw.println(9);
                    good = true;
                    break;
                }
            }
            if (!good) {
                char[] ans = solve(s);
                pw.println(ans.length);
                for (char a : ans) {
                    pw.print(a);
                }
                pw.println();
            }

        }

        pw.close();
    }

    static void build() {
        list = new ArrayList<>();
        list.add(1);
        for (int i = 2; i <= 1000; i++) {
            if (!isPrime[i]) {
                if (valid(i)) list.add(i);
            }
        }
    }

    static char[] solve(char[] s) {
        String ans = "";
        for (int i = 0; i < list.size(); i++) {
            char[] m = Integer.toString(list.get(i)).toCharArray();
            int indx = m.length - 1;
            for (int j = s.length - 1; j >= 0; j--) {
                if (s[j] == m[indx]) indx--;
                if (indx == -1) return m;
            }
            //debug(indx, m);
            if (indx == -1) return m;
        }
        return new char[1];
    }

    static boolean valid(int n) {
        while (n != 0) {
            if (n % 10 == 4) return false;
            if (n % 10 == 6) return false;
            if (n % 10 == 8) return false;
            if (n % 10 == 9) return false;
            if (n % 10 == 0) return false;
            n /= 10;
        }
        return true;
    }

    static void sieve() {
        isPrime = new boolean[N + 5];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= N; i++) {
            if (!isPrime[i]) continue;
            for (int j = i * i; j <= N; j += i) {
                isPrime[j] = false;
            }
        }
    }

    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }
}
