Ще одна нова функція
Функція ϕ(n) або phi(n), також відома як функція Ейлера, визначається як кількість додатних цілих чисел, які не перевищують 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).