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.

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