Một phân số được gọi là phân số tối giản nếu ước chung lớn nhất của tử số và mẫu số bằng 1.

Yêu cầu: Cho trước một số nguyên dương $N$. Hãy đếm xem có bao nhiêu phân số dương bé hơn 1, có mẫu là $N$ và là phân số tối giản.

Dữ liệu

• Chứa một số nguyên dương $N$ ($N\le {10}^{16}$).

Kết quả

• Ghi ra số nguyên $M$ là số lượng phân số theo yêu cầu trên

Sample Input

9

Sample Output

6

Giải thích: Có 6 phân số dương bé hơn 1 có mẫu bằng 9 và là phân số tối giản là $\frac{1}{9};\frac{2}{9};\frac{4}{9};\frac{5}{9};\frac{7}{9};\frac{8}{9}$

Cho một dãy gồm $N$ số nguyên dương $A_1,A_2,\dots ,A_N$.($N\le {10}^4,A_i\le {10}^9$) và số $K$ ($K\le N$). Hãy in ra số nhỏ thứ $K$ trong dãy.

Input

• Dòng đầu chứa số $N,K$,
• Dòng thứ hai chứa $N$ số nguyên dương $A_1,A_2,\dots ,A_N$.

Output

• Một dòng chứa dãy số nhỏ thứ $K$ trong dãy.

Input

6 4    
91 451 43 3 452 54

Output

91

Quý rất thích làm toán. Quý thách đố bạn bài sau: Cho số tự nhiên $n$. Hãy tính tổng $1-2+3-4+...n$.

Input: Gồm một số tự nhiên $n$.

Output: In ra một số nguyên là đáp số của tổng trên.

Ví dụ

Input1

4

Output1

-2

Input2

5

Output2

3

Giải thích:

• Trong test ví dụ 1, $1-2+3-4=-2$
• Trong test ví dụ 2, $1-2+3-4+5=3$

Subtasks

• Có $50\mathrm{\%}$ số điểm tương ứng với $n\le {10}^6$
• Có $50\mathrm{\%}$ số điểm tương ứng với $n\le {10}^9$