Gryffindor was fourth in the points table with 312 points and Slytherin in first place with 482 points. But Professor Dumbledore gave last minute points to students, where Ron got 50 points, Hermione 50, Harry 60 and Neville 10 points for Gryffindor so they tied with Slytherin. Now both Gryffindor and Slytherin need only one point to win the house cup. So professor Dumbledore gives them a task, the house that solves the task first will get one point and also win the House Cup.

There are three numbers given X, Y and K. The task is to find how many numbers from 1 to K can be divided by X or Y but not divisible by (X+Y). Now you are only a programmer from Gryffindor house, all they come to you for the solution. Help Gryffindor to win the House Cup.

Input starts with an integer T — denoting the number of test cases.
The first line of each test cases contain three integer X, Y and K.

\(1 <= T <= 10^5\)
\(1 <= X, Y, K <= 10 ^ 7\)

Print a single integer – how many numbers from 1 to K are divisible by X or Y but not divisible by (X+Y).

Input copy	Output copy
5 2 3 12 2 2 4 6 12 15789 5 7 50000 578 679 10000000	7 1 1754 14405 31979