Kunal loves Puja Vacation . But this time he is getting bored .
Reason ? Ask Kunal
So , he started playing a game .
The rules are as follow
->He took three primes a , b and c.
->He took all the multiples of prime and put in a container
->Then , he sorts the container in non decending order
->Then , he removes all the duplicates

Now he want to find Kth number of the container

Kunal is unable to think these days.so, he want your help
Can you help him out?

Input:

First line contains T, the number of test cases that follow. Next T lines, each contains three prime a , b, c and K.

Output: For each test case, print the desired result in separate lines.

Constraints:
1 ≤ T ≤ 100000
0 ≤ K ≤ 1000000000000000
1 ≤ a,b,c ≤ 10000