SP27248 FUNMODSEQ - Funny Modular Sequence

Lets define a funny modular sequence as a sequence such that a $ _{1} $ x a $ _{2} $ =1 (mod p), a $ _{2} $ x a $ _{3} $ =1 (mod p) ..., a $ _{n-1} $ x a $ _{n} $ = 1 (mod p). Also, a $ _{1} $ , a $ _{ 2} $ , a $ _{ 3} $ , ... a $ _{n} $ must be less than p and greater than or equal to 0. Given one element, a $ _{1} $ , find the sum of the entire funny modular sequence of length n. If, for any a $ _{i} $ , where i>=1, there exists no a $ _{i+1} $ such that a $ _{i} $ x a $ _{i+1} $ = 1 (mod p), output -1. **Note**: p is not necessarily prime. Input: The first line contains T, the number of test cases. T lines follow, each containing a $ _{1} $ , p, and n. Output: For each test case, output one line, the required sum. Constraints: 1

N/A

N/A