Subh finally proposed to his long time girlfriend. His girlfriend was however not happy with his style. From the previous question we know that our Subh is a coder so he has to propose in a coder's style. So Subh makes another attempt and says the following which I quote :-

I love you. My love for you is not a m==0 night stand. It is equal to the number of DISTINCT values of (ax+b)%m possible for your favorite a,b and m.

Now you are answering this question in Subh's perspective :P. She is giving you a,b and m and you have to get the right answer. Keep in mind she knows the answer too otherwise why would Subh propose like that??

Further this question has no partial marking. Why because you can't give wrong answer while proposing.

CONSTRAINTS:

1<=t<=10^5

-10^9<=a<=10^9

-10^9<=b<=10^9

-10^9<=m<=10^9

m!=0

INPUT FORMAT:

First Line contains number of test cases t.

For next t lines:

each line contains three integers which are her favorite a,b,m.

OUTPUT FORMAT:

For t lines:

Print on each line, number of distinct values (ax+b)%m.