Еще одна новая функция
Функция ϕ(n) или phi(n), также называемая функцией Эйлера, определяется как количество положительных целых чисел ≤ n, которые являются взаимно простыми (то есть не содержат каких-либо общих множителей) с n, где 1 считается взаимно простым со всеми числами. Например, есть восемь чисел, взаимно простых с 24 (1, 5, 7, 11, 13, 17, 19 и 23), поэтому ϕ(24) = 8.
Глубиной phi значения числа назовем количеством шагов, которое следует выполнить для получения 1. Рассмотрим пример.
ϕ(13) = 12 . . . шаг 1
ϕ(12) = 4 . . . шаг 2
ϕ(4) = 2 . . . шаг 3
ϕ(2) = 1 . . . шаг 4
Глубина phi(13) равна 4. Назовем эту функцию depthphi. Таким образом можно записать что depthphi(13) = 4. Сумма функции depthphi (SODF) принимает в качестве аргументов два целых числа и определяется следующим образом:
По заданным числам m и n вычислите значение SODF(m, n).
Входные данные
Первая строка содержит целое число n (0 < n < 2001), которое указывает на количество тестов. Каждая из следующих n строк содержит два целых числа m и n (2 ≤ m ≤ n ≤ 2000000).
Выходные данные
Для каждого теста в отдельной строке выведите одно целое число - значение SODF(m, n).