Функция ϕ(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).