How do I optimize a piece of code to execute under 2 seconds

For a coding practice challenge I wrote this python code, but is giving 6 seconds of execution time but I want it to execute under 2 seconds. How should I modify this code? Future tips also welcomed.

times = int(raw_input())

for i in range (times):
    count = 0
    z =  raw_input().split()
    a,d = int(z[0]),int(z[1])
    p= int(raw_input())
    while a%p != 0:
        a= a+d
        count = count+1
    print count

Brief of the problem statement:

Input format: The first line contains a number, tc, denoting the number of test cases. The second line contains two integers, a and d - a depicts the first term in the AP, d depicts the common difference. The last line contains the prime number.

Output format: You have to print the FIRST index (0-based) of the multiple of the given prime number in the given AP. If no such element exists in this infinite AP, then print -1.

Constraints:

0 <= a, d, <= 10^18
1 <= p <= 10^9

Sample Input:

1
4 9
11

Sample Output:

2

Explanation: the AP would be: 4, 4+9=13, 13+9=22, 22+9=31 - and the prime number is 11, so the index is [2].

Answers

You forgot to change p%a to a%p, which was pointed out the last time you posted this question. You also forgot to clarify that it takes six seconds with the real data, not this test data.

The problem is that you're using an inefficient, brute-force algorithm. Try the extended Euclidean algorithm.

Need Your Help