751. Multiples Party

0

Easy

You are hosting a party and want to give party favors to guests who have brought both sweets and drinks. There are a total of

**z**guests, with**n**guests bringing sweets and**m**guests bringing drinks. To determine the number of guests who brought both, you need to find the count of integers**x**such that**x<=z**,**x%m ==0**, and**x%n==0**. Your task is to calculate this count for each test case.Input Format

The first line of input consists of the number of test cases,

Each test case consists of three integers:

**t**.Each test case consists of three integers:

**n**,**m**, and**z**.Output Format

For each test case, output a single integer representing the number of guests who brought both sweets and drinks.

Example

Input

2
4 8 9
1 1 10

Output

1
10

Constraints

1 <= t <= 10^5
1 <= n,m <= 10^9
1 <= z <= 10^18

Loading...

View Submissions

Console