In 1960, Donald Wall of IBM, in Phite Plains, NY, proved that the series obtained by taking each element of the \textit{Fibonacci} series modulo \textbf{m }was periodic. For example, the first ten element of the \textit{Fibonacci} sequence, as well as their remainders modulo \textbf{11}, are: The sequence made up of the remainders then repeats. Let \textbf{k(m)} be the length of the repeating subsequence; in this example, we see \textbf{k(11)} = \textbf{10}. Wall proved several other properties, some of which you may find interesting: \begin{itemize} \item If \textbf{m }> \textbf{2}, \textbf{k(m)} is even. \item For any even integer \textbf{n }> \textbf{2}, there exists \textbf{m} such that \textbf{k(m)} = \textbf{n}. \item \textbf{k(m)} ≤ \textbf{m^2 - 1} \item \textbf{k(2^n) }≤\textbf{ 3 * 2^\{(n-1)\}} \item \textbf{k(5^n) = 4 * 5^n} \item \textbf{k(2 * 5^n)} = \textbf{6n} \item If \textbf{n} > \textbf{2}, \textbf{k(10n)} = \textbf{15 * 10^\{(n-1)\}} \end{itemize} For this problem, you must write a program that calculates the length of the repeating subsequence \textbf{k(m)} for different modulo values \textbf{m}. \InputFile The first line contains the number of data set \textbf{p }(\textbf{1 }≤ \textbf{p }≤ \textbf{1000}) that follow. Each data set is a single line that consists of two space separated integer values \textbf{n }and \textbf{m}, where \textbf{n }is the data set number and \textbf{m }(\textbf{2 }≤ \textbf{m }≤ \textbf{1000000}) is the modulo value. \OutputFile For each data set there is one line of output. It contains the data set number \textbf{n }followed by a single space, followed by the length of the repeating subsequence for \textbf{m} - the value of \textbf{k(m)}.