Queries About Numbers
Этибар очень любит числа. Теперь пришло время решить новую задачу.
Задано натуральное число N. Ему следует ответить на Q вопросов вида T K. Здесь T - тип запроса, K - натуральное число.
Если T = 1, он должен найти количество натуральных чисел, являющихся одновременно делителями N и K.
Если T = 2, он должен найти количество натуральных чисел, являющихся делителями N и которые делятся на K.
Если T = 3, он должен найти количество натуральных чисел, являющихся делителями N и которые не делятся на K.
Etibar can solve all these queries, but you will be hungry for night if this happens, because He will not have free time to do it. Therefore you compromise with him and decided that everyone must do his own job. You must program and our hero must do his own works.
Входные данные
Первая строка содержит 2 числа: N и Q (1 ≤ N ≤ 10^12, 1 ≤ Q ≤ 5*10^5). Далее следуют Q строк, каждая из которых содержит 2 числа: T и K (1 ≤ T ≤ 3, 1 ≤ K ≤10^12).
Выходные данные
Для каждой из Q строк вывести в отдельной строке ответ на соответствующий запрос.