358. Multiples Again

0

Easy

Imagine you are organizing a party and want to give party favors to guests who have brought both sweets and drinks. You have a total of

**z**guests, and**n**guests have brought sweets, and**m**guests have brought drinks. You want to know how many guests brought both sweets and drinks, so you ask your friend to count the number of guests x such that x<=z and x%m ==0 and x%n==0. Your friend comes back with the answer - the number of guests who brought both sweets and drinks is equal to the number of integers**x**such that**x<=z**and**x%m ==0**and**x%n==0**.Input Format

The first line consists of number of test cases t.

Every test case consists of 3 intgers n , m ,z.

Every test case consists of 3 intgers n , m ,z.

Output Format

Answer to every test case a single integer.

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