python - find if a number divisible by the input numbers -

given 2 numbers , b, have find nth number divisible or b.

the format looks below:

input : first line consists of integer t, denoting number of test cases. second line contains 3 integers a, b , n

output : each test case, print nth number in new line.

constraints :

1≤t≤105

1≤a,b≤104

1≤n≤10

sample input

1

2 3 10

sample output

15

explanation

the numbers divisible 2 or 3 are: 2,3,4,6,8,9,10,12,14,15 , 10th number 15

my code

test_case=input()  if int(test_case)<=100000 ,  int(test_case)>=1:     p in range(int(test_case)):         count=1         j=1          inp=list(map(int,input().strip('').split()))         if inp[0]<=10000 ,  inp[0]>=1 ,  inp[1]<=10000 ,  inp[1]>=1 , inp[1]<=1000000000 ,  inp[1]>=1:             while(true ):              if count<=inp[2] :                k=j                if j%inp[0]==0 or j%inp[1] ==0:                    count=count+1                    j=j+1                 else       :                    j=j+1              else:                  break             print(k)              else:             break 

problem statement: single test case input 2000 3000 100000 taking more 1 second complete.i want if can results in less 1 second. there time efficient approach problem,may if can use data structure , algorithms here??

for every 2 numbers there number k such k=a*b. there many multiples of a , b under k. set can created so:

s = set(a*1, b*1, ... a*(b-1), b*(a-1), a*b) 

say take values a=2, b=3 s = (2,3,4,6). these possible values of c:

[1 - 4]  => (2,3,4,6) [5 - 8]  => 6 + (2,3,4,6) [9 - 12] => 6*2 + (2,3,4,6) ...  

notice values repeat predictable pattern. row can take value of c , divide length of set s (call n). set index mod of c n. subtract 1 1 indexing used in problem.

row = floor((c-1)/n) column = `(c-1) % n` result = (a*b)*row + s(column)   

python impl:

a = 2000 b = 3000 c = 100000 s = list(set([a*i in range(1, b+1)] + [b*i in range(1, a+1)])) print((((c-1)//len(s)) * (a*b)) + s[(c - 1)%len(s)])