Etibar loves number theory very much. Now it is time to solve a new kind of problem. There is given a natural number \textbf{N}. He has to answer \textbf{Q} queries of the form \textbf{T K}. Here \textbf{T} is the type of query and \textbf{K} is the natural number. If \textbf{T} = \textbf{1}, He must find the number of natural numbers which is divisor of both \textbf{N} and \textbf{K}. If \textbf{T} = \textbf{2}, He must find the number of natural numbers which is divisor of \textbf{N} and is divisible by \textbf{K}. If \textbf{T} = \textbf{3}, He must find the number of natural numbers which is divisor of \textbf{N} and is not divisible by \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 There will be \textbf{2} numbers in the first line: \textbf{N} and \textbf{Q} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^12}, \textbf{1} ≤ \textbf{Q} ≤ \textbf{5*10^5}). \textbf{Q} lines follow with \textbf{2} numbers each: \textbf{T} and \textbf{K} (\textbf{1} ≤ \textbf{T} ≤ \textbf{3}, \textbf{1} ≤ \textbf{K} ≤\textbf{10^12}). \OutputFile For each of the \textbf{Q} lines you must output the result for corresponding query in separate line.