The entrance of the contest => link

A. The Miracle and the Sleeper

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

Problem

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

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

Input

Each test contains multiple test cases.

The first line contains one positive integer t (1≤t≤1041 \leq t \leq 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≤1091 \leq l \leq r \leq 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≥lr \geq a \geq b \geq l.

Example

input

1
2
3
4
5
4
1 1
999999999 1000000000
8 26
1 999999999

output

1
2
3
4
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=0a \bmod b = 1 \bmod 1 = 0.

In the second test case, the optimal choice is pair (a,b)=(1000000000,999999999), for which a mod b=1a \bmod b = 1.

Solution

It’s pretty ez to determine that a mod ba \bmod b gets its max value as long as b=a/2+1b = a / 2 + 1.

Consider a as a determined constant value.

Supposing we got a mod b=za \bmod b = z and a/b=ka / b = k(noticing that k≥1k \geq 1 shoud stand as long as we have a≥ba \geq b), therefore we have a=b∗k+z(k≥1)a = b * k + z(k \geq 1) and b>zb \gt z

Therefore we got a=b∗k+z≥b+z>2∗za = b * k + z \geq b + z \gt 2 * z, which means z<⌜a/2.0⌝z \lt \ulcorner a / 2.0 \urcorner, that z should never be greater than or equals to half of a.

Meanwhile when we have b=a/2+1b = a / 2 + 1, z in consequence equals a−a/2−1a - a / 2 - 1, which happens to be the best scenario to maximize z.

Q.E.D.

As a gets larger, z in the consequence gets larger as well. Seems pretty ez, but what if when a gets its maximum value which is r, meanwhile b still cannot satisfy the condition b≥lb \geq l?

Considering right now we have z=a−k∗b≤a−bz = a - k * b \leq a - b, still b should equal to l to maximize z.

The code follows below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package com.company;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int caseNum = scanner.nextInt();
        for(int i = 0; i < caseNum; i++){
            System.out.println(new Main().solve(scanner));
        }
    }

    private int solve(Scanner scanner) {
        int l = scanner.nextInt();
        int r = scanner.nextInt();
        int b = r / 2 + 1;
        b = Math.max(l, b);
        return r % b;
    }
}

seems good for now

B. Scenes From a Memory

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

Problem

During the hypnosis session, Nicholas suddenly remembered a positive integer nn, which doesn’t contain zeros in decimal notation.

Soon, when he returned home, he got curious: what is the maximum number of digits that can be removed from the number so that the number becomes not prime, that is, either composite or equal to one?

For some numbers doing so is impossible: for example, for number 5353 it’s impossible to delete some of its digits to obtain a not prime integer. However, for all n in the test cases of this problem, it’s guaranteed that it’s possible to delete some of their digits to obtain a not prime number.

Note that you cannot remove all the digits from the number.

A prime number is a number that has no divisors except one and itself. A composite is a number that has more than two divisors. 11 is neither a prime nor a composite number.

Input

Each test contains multiple test cases.

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

The first line of each test case contains one positive integer k (1≤k≤501 \leq k \leq 50) — the number of digits in the number.

The second line of each test case contains a positive integer nn, which doesn’t contain zeros in decimal notation (10k−1≤n<10k10^{k−1} \leq n \lt 10^k). It is guaranteed that it is always possible to remove less than kk digits to make the number not prime.

It is guaranteed that the sum of kk over all test cases does not exceed 10410^4.

Output

For every test case, print two numbers in two lines. In the first line print the number of digits, that you have left in the number. In the second line print the digits left after all deletions.

If there are multiple solutions, print any.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
7
3
237
5
44444
3
221
2
35
3
773
1
4
30
626221626221626221626221626221

output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
27
1
4
1
1
2
35
2
77
1
4
1
6

Note

In the first test case, you can’t delete 22 digits from the number 237237, as all the numbers 22, 33, and 77 are prime. However, you can delete 11 digit, obtaining a number 27=3327=3^3.

In the second test case, you can delete all digits except one, as 4=224=2^2 is a composite number.

Solution

According to the problem, we need to delete as many digits as possible so that the number is not a prime.

Therefore we have :

  • If the number contains any digit of ‘1’, ‘4’, ‘6’, ‘8’, ‘9’, which is not a prime itself, in the best scenario, we can delete every other digits but this one. With one digit remaining.
  • Otherwise we have to consider the condition where we have two digits left. Obviously when the same digit appears for more than once, we can keep only this two digits as the number ‘kk’ is not a prime (kk=k∗11kk = k * 11)
  • Otherwise? The left scenario is where the digits ‘2’, ‘3’, ‘5’, ‘7’ each appears for no more than once.
    • For any multi-digit number ending with ‘2’ or ‘5’ is not a prime, therefore if there is any digit comming before ‘2’ or ‘5’ we only keep two digits left.
    • For any two-digit number ending with ‘7’, only ‘57’ and ‘27’ are not primes. Therefore if we have two of these digits, we keep two of them.

The code follows below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package com.company;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int caseNum = scanner.nextInt();
        for(int i = 0; i < caseNum; i++){
            System.out.println(new Main().solve(scanner));
        }
    }

    private String solve(Scanner scanner) {
        int len = scanner.nextInt();
        String num = scanner.next();
        int[] cnt = new int[9];
        for(int i = 0; i < len; i++){
            char ch = num.charAt(i);
            if(ch == '1' || ch == '4' || ch == '6' || ch == '8' || ch == '9') {
                System.out.println(1);
                return Character.toString(ch);
            }
        }
        for(int i = 0; i < len; i++){
            char ch = num.charAt(i);
            if(++cnt[ch - '1'] == 2) {
                System.out.println(2);
                return ch + Character.toString(ch);
            }
        }
        Arrays.fill(cnt, 0);
        for(int i = 0; i < len; i++){
            char ch = num.charAt(i);
            if((ch == '2' || ch == '5') && i != 0){
                System.out.println(2);
                return num.substring(i - 1, i + 1);
            }
            if(ch == '7' && cnt['2' - '1'] > 0) {
                System.out.println(2);
                return "27";
            }
            if(ch == '7' && cnt['5' - '1'] > 0) {
                System.out.println(2);
                return "57";
            }
            ++cnt[ch - '1'];
        }
        return "";
    }
}

oops