SP14175 AFSK - Power Factor Sum Sum (hard)

Here is a mixed edition of [Divisor Summation Powered](http://www.spoj.com/problems/IITD4/) and [Amazing Factor Sequence (medium)](http://www.spoj.com/problems/AFS2/).

First line of input contains an integer **_T_**, the number of test cases. Each of the next **_T_** lines contains three integers **_n, k, m_**.

For each test case, print **_a $ _{k} $ \[n\]_** on a single line. As the answer could be a big number, you just have to output it modulo **_m_**.