We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Mathematics
  3. Number Theory
  4. Little Panda Power

Little Panda Power

Problem
Submissions
Leaderboard
Discussions
Editorial

Little Panda has a thing for powers and modulus and he likes challenges. His friend Lucy, however, is impractical and challenges Panda to find both positive and negative powers of a number modulo a particular number. We all know that refers to the modular inverse of modulo (see Wikipedia).

Since Lucy is impractical, she says that for .

Now she wants Panda to compute .

She also thinks that this problem can be very difficult if the constraints aren't given properly. Little Panda is very confused and leaves the problem to the worthy programmers of the world. Help him in finding the solution.

Input Format
The first line contains , the number of test cases.
Then lines follow, each line containing , and .

Output Format
Output the value of .

Constraints




and are coprime to each other (see Wikipedia)

Sample Input

3  
1 2 3  
3 4 2  
4 -1 5

Sample Output

1  
1  
4  

Explanation
Case 1:
Case 2:
Case 3:

Author

aka_007

Difficulty

Hard

Max Score

30

Submitted By

3081

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature