InternDoor

The n-th multiple of either number

Mediumbinary search · mathRead the input, print the output

Reported in interviews at (where)

List, from the smallest up, every positive whole number that is divisible by a, by b, or by both. A number divisible by both is listed once.

For each test, print the n-th number in that list. n can be as large as a billion, so walking the list one number at a time is far too slow.

Input

The first line holds T, the number of tests. Each test is one line holding three whole numbers: a, b and n.

Output

For each test, one line: the n-th number divisible by a or by b.

Example
Input
3
3 5 6
4 6 5
7 7 3
Output
12
16
21
  1. The list starts 3, 5, 6, 9, 10, 12: the sixth number is 12.
  2. The list starts 4, 6, 8, 12, 16: 12 is divisible by both and is listed once.
  3. With a and b the same, the list is just the multiples of 7.

Limits

  • 1 <= T <= 1000
  • 1 <= a, b <= 40000
  • 1 <= n <= 1000000000

Hints

Hint 1

How many numbers from 1 to x are in the list? x / a of them divide by a and x / b by b, but the ones divisible by both were counted twice: those are the multiples of the least common multiple of a and b.

Hint 2

That count only grows as x grows, so binary search for the smallest x whose count reaches n. The answer is at most n times the smaller of a and b.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.