Этибар очень любит числа. Теперь пришло время решить новую задачу. Задано натуральное число \textbf{N}. Ему следует ответить на \textbf{Q} вопросов вида \textbf{T K}. Здесь \textbf{T} - тип запроса, \textbf{K} - натуральное число. Если \textbf{T} = \textbf{1}, он должен найти количество натуральных чисел, являющихся одновременно делителями \textbf{N} и \textbf{K}. Если \textbf{T} = \textbf{2}, он должен найти количество натуральных чисел, являющихся делителями \textbf{N} и которые делятся на \textbf{K}. Если \textbf{T} = \textbf{3}, он должен найти количество натуральных чисел, являющихся делителями \textbf{N} и которые не делятся на \textbf{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. \InputFile Первая строка содержит \textbf{2} числа: \textbf{N} и \textbf{Q} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^12}, \textbf{1} ≤ \textbf{Q} ≤ \textbf{5*10^5}). Далее следуют \textbf{Q} строк, каждая из которых содержит \textbf{2} числа: \textbf{T} и \textbf{K} (\textbf{1} ≤ \textbf{T} ≤ \textbf{3}, \textbf{1} ≤ \textbf{K} ≤\textbf{10^12}). \OutputFile Для каждой из \textbf{Q} строк вывести в отдельной строке ответ на соответствующий запрос.