Vasya loves to program. He also loves science fiction. Once on vacation, having read books with his friend, Petya, Vasya decided to devise a formula showing the growth of population on Mars. By estimations Wasi after \textbf{N} years of life, the world population of Martians should be \textbf{S_N}_\{ \}Martians, where \textbf{S_N}_\{ \}determined by the formula: \includegraphics{https://static.e-olymp.com/content/ec/ec86af1d8bf3d63cb1a5913a0ec4269d91ebdbe6.jpg} Peter, after Vasya told him his theory, doubts and decided to calculate this number on your computer to verify its authenticity. Moreover, Peter recently read an intelligent book on programming, so he thinks that it does not take much time. You are invited to do the same, but without having to read smart books. Note that for your convenience to bring \textbf{S_N} modulo \textbf{M}. \InputFile The first line of input contains the number of tests. For each test in a separate row contains the number \textbf{N} -- the age of the planet Mars and the number of \textbf{M} - module. \textbf{0} < \textbf{N} <= \textbf{1000000000}, \textbf{0} < \textbf{M} <= \textbf{1000000000}. \OutputFile For each test in the output file will contain the string containing the expected number of Martians after \textbf{N} years of life on the planet of \textbf{M}.