You are given a set of n numbers , a key p , a end product q.

You have to convert key p to end product q in minimum number array elements of size n

Whenever you choose an element from the array p gets redefined as p = (p*current_element)%(10^5)

using the above operation p has to be converted to q using minimum elements.

for eg

n = 4 , p = 6 , q = 60

array = [2,5,7,10]

answer here would be 1 since (6*10)%(10^5) = 60 = q.

I thought of a BFS approach to this but as n increases the time becomes exponential how can i reduce the time for this.