Проще простого
ограничение по времени на тест
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
1482488 1582487