ЕЖЕГОДНАЯ ОЛИМПИАДА ПО ПРОГРАМИРОВАНИЮ В ЛИЧНОМ ЗАЧЁТЕ

11 мая регистрация участников на сайте http:\olimp.bstu.by
Дата проведения 17 мая
Время проведения с 9:00 до 12:00

 
HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > VIII ОЛИМПИАДА БрГТУ ПО ПРОГРАММИРОВАНИЮ ДЛЯ ШКОЛЬНИКОВ - очный тур > problem:


F. Проще простого

VIII ОЛИМПИАДА БрГТУ ПО ПРОГРАММИРОВАНИЮ ДЛЯ ШКОЛЬНИКОВ - очный тур

Start: Feb.26.2022 at 10:30:00 AM
Finish: Feb.26.2022 at 01:30:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (2)

Contest problems

• A. Подсчёт столбов
• B. В гору пойдет!
• C. Развивающие игры
• D. Вечеринка в Нью-Йорке
• E. Сладкоежка
• F. Проще простого

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/2000/2000/2000 ms. Memory limit 256000/256000/256000/256000 Kb.

Проще простого
Проще простого
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
primes.in
вывод
primes.out

Что может быть проще простого числа? Казалось бы, объяснить, что такое простое число, можно даже человеку, совершенно далёкому от математики: целое число называется простым, если оно не меньше двух и не делится ни на какое целое положительное число, кроме единицы и самого себя. Это определение будет понятно даже третьекласснику, только-только познакомившемуся с делением. Что может быть проще? Но, как часто случается в математике, за кажущейся простотой определения скрывается очень глубокая теория с множеством нетривиальных фактов, многие из которых остаются недоказанными и по сей день.

Прочитав популярную книгу Д. Дербишира «Простая одержимость», Леопольд узнал следующий занятный факт. Оказывается, существует Теорема о распределении простых чисел, гласящая, что количество простых чисел, не превышающих N, можно очень точно оценить как . Например, начиная с N > 5000, эта формула даёт ошибку, не более чем в 15% от реального значения. Более того, с ростом N относительная погрешность такой оценки падает, стремясь к нулю.

Леопольд крайне заинтересовался простыми числами и связанной с ними теорией. Он решил выдвинуть какую-нибудь не менее важную и серьёзную гипотезу, а потом доказать её, и назвать полученный факт теоремой Леопольда. Для этого ему нужна помощь в отыскании закономерностей, описывающих простые числа. Он просит вас написать для него программу, которая ищет для него Q отрезков, i-й из которых состоит из Li последовательных натуральных чисел и содержит определённое количество Ki простых чисел. Для простоты анализа он просит вас ограничиться в поисках первыми десятью миллионами чисел. Помогите ему, и, возможно, вам с ним удастся оставить след в истории!

Входные данные

В первой строке входного файла задано целое число Q (1 ≤ Q ≤ 100 000) "— количество отрезков, которые требуются Леопольду.

В каждой из последующих Q строк задано по два целых числа L и K (7000 ≤ K ≤ L ≤ 100 000). Обратите внимание, подобные ограничения даны не случайно: Леопольд знает, что нередко закономерности начинают проявляться только при больших значениях.

Выходные данные

На каждый запрос Леопольда выведите в отдельной строке начальное и конечное число требуемого отрезка, либо  - 1, если его не существует среди первых десяти миллионов чисел. Если требуемых отрезков несколько, выведите любой.

Примеры

Входные данные

Выходные данные

3

8000 8000

80000 7654

100000 7000

-1

3632 83631

100000 7000

 

Для отправки решений необходимо выполнить вход.

www.contester.ru