3681 - Three-Primed Intervals

Created by Luis Manuel Díaz Barón
Added by luismo (2016-06-07)
Limits
Total Time: 18000 MS | Test Time: 1500 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Given two integers A and B, you must print the length of the shortest interval [C, D] containing 3 prime numbers that is completely contained in the interval [A, B], that is, A C < D B. If such interval does not exist, you must print -1.
Dados dos números enteros A y B, usted debe imprimir la longitud del intervalo más pequeño [C, D] que contenga 3 números primos y que esté completamente contenido dentro del intervalo [A, B], es decir, A C < D B. Si dicho intervalo no existe, usted debe imprimir -1.
Given two integers A and B, you must print the length of the shortest interval [C, D] containing 3 prime numbers that is completely contained in the interval [A, B], that is, A C < D B. If such interval does not exist, you must print -1.

Input specification

The first line contains a single integer T (1 T 105). Each of the next T lines contains two space separated integers A (1 A 106) and B (A B 106).
La primera línea de entrada contiene un número entero T (1 T 105). Cada una de las siguientes T líneas contiene dos números enteros A (1 A 106) y B (A B 106) separados por un espacio.
The first line contains a single integer T (1 T 105). Each of the next T lines contains two space separated integers A (1 A 106) and B (A B 106).

Output specification

For each test case, print a single line containing the length of the shortest interval containing 3 prime numbers that is completely contained inside the interval [A, B] or -1 if such interval does not exist.
Por cada caso, usted debe imprimir una línea con la longitud del intervalo más pequeño que contenga 3 números primos y que esté completamente contenido dentro del intervalo [A, B] o -1 si dicho intervalo no existe.
The first line contains a single integer T (1 T 105). Each of the next T lines contains two space separated integers A (1 A 106) and B (A B 106).

Sample input

3
1 10
10 20
5 10

Sample output

4
7
-1

Hint(s)