Студенту снится сон. Во сне он ходит по городу, в котором ужасно много трактиров. В каждом трактире выпивает кружку эля. Все трактиры пронумерованы целыми положительными числами, и из трактира с номером n можно пойти только в трактир с номером, который делится на n. Начинается сон в трактире с номером a. Студент знает, что ему надо попасть в трактир с номером b. При этом, понятно, хочет по пути выпить как можно больше эля. Если он не может дойти из трактира a в трактир b, то сразу просыпается в холодном поту.

В первой строке дано T — количество тестов, далее идут T строк с числами a и b (0 ≤ T ≤ 20; 1 ≤ a, b ≤ 10⁹)

Для каждого теста в отдельной строке выведите максимальное количество кружек, которое студент может выпить по пути.