Hi, I had a python solution to the problem based on baby-step giant-step algorithm to find discrete log but I got TLE, if someone can help me to optimize the solution, thanks in advance.

""" Here I show how to find a discrete log using baby step big step algorithms, Code """

def gcd(a,b): if a%b==0:return b,0,1 r,x,y=gcd(b,a%b) return r,y,x-(a/b)*y

def inv(a,b,m): k=(a**2-5*b**2)%m g,k,_=gcd(k,m) k%=m if g!=1:return None return ((a*k)%m,(-b*k)%m)

def pow(x,n,one,mul):

r=one
while n:
    if n%2:r=mul(r,x)
    n/=2
    x=mul(x,x)
return r

import math

def dLog(x,y,one,mul,inv,group_size): step=int(math.sqrt(group_size))+1

xinv=inv(x)
if not xinv:return -1
r=y
d={}
for i in range(1,step+1):
    r=mul(r,xinv)
    if r not in d:d[r]=i

current=one
ret=step**2+1

r=pow(x,step,one,mul)

for i in range(0,step+1):       
    if current in d:            
        ret=min(i*step+d[current],ret)
    current=mul(current,r)
return -1 if ret==step+1 else ret

def solve(a,b,m):

def mul(v1,v2):
    a1,b1=v1
    a2,b2=v2
    return ((a1*a2+5*b1*b2)%m,(a1*b2+b1*a2)%m)


return dLog((a,b),(1,0),(1,0),mul,lambda v:inv(v[0],v[1],m),m*m)

T=input()

for i in range(T): a,b,m=map(int,raw_input().strip().split()) print solve(a,b,m)