Простые отары
На джайлоо у реки Чон-Кемин пасутся отары двух чабанов. В отаре Бакыта животные пронумерованы числами от 1 до A, у Эрлана — от 1 до B. Ветеринар осматривает пары животных (x, y): x из отары Бакыта, y из отары Эрлана. Пару он называет «простой», если наибольший общий делитель номеров НОД(x, y) — простое число.
Ответьте на q вопросов: сколько простых пар при данных A и B?
Входные данные
В первой строке — число q (1 ≤ q ≤ 5000). В каждой из следующих q строк — два целых числа A и B (1 ≤ A, B ≤ 10⁷).
Выходные данные
Для каждого вопроса выведите количество пар (x, y), 1 ≤ x ≤ A, 1 ≤ y ≤ B, у которых НОД(x, y) — простое число.
Пример 1
Вход:
3
4 4
10 7
1 100
Выход:
4
20
0
Пояснение
При A = B = 4 подходят пары (2, 2), (2, 4), (4, 2), (3, 3) — у них НОД равен 2 или 3. У пары (4, 4) НОД равен 4, это не простое число.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 15 % тестов A, B ≤ 300, ещё в 10 % тестов A, B ≤ 10⁶.
Подсказка
Функция Мёбиуса: Σ μ(d) по всем делителям d числа m равна 1 при m = 1 и 0 иначе.
Комментарии