Product Codes - Ma hang hoa (But Wait, There Are Some Changes Version)


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 500M

Author:
Problem type
Allowed languages
Assembly, C, C++, Java, Pascal, Perl, Python, Text

Company E specializes in mass-producing products on an assembly line. When products are placed on the conveyor belt for the final finishing steps, each product is assigned an ID code for tracking. The ID of each product is a positive integer corresponding to its sequential position as it enters the conveyor belt.

Due to overdue maintenance, two processing stages on the conveyor belt are technically faulty. In the first stage, every \(a\)-th product processed is defective. In the second stage, every \(b\)-th product processed is defective. Consequently, any product with an ID divisible by \(a\) or divisible by $b$ is defective, and the automated system rejects it. During a shift, an operator wants to know how many defective products there are among the first \(N\) products produced.

Input

  • A single line containing three positive integers \(a, b, N \ (2 \le a, b \le 10^9; 2 \le N \le 10^{18})\).

Output

  • A single integer representing the total number of defective products.

Scoring

  • Subtask 1 (70%): \(N \le 10^6\).
  • Subtask 2 (30%): No additional constraints.

Examples

Example 1

input

2 5 23

output

13

Explanation

The defective products with IDs not exceeding 23 are: 2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 20, 22 (a total of 13 defective products).


Comments

There are no comments at the moment.