Ôn tập THTA Phương·

Số nguyên dương \(n\) được gọi là số nguyên tố nếu nó có đúng \(2\) ước dương là \(1\) và \(n\).

Viết chương trình kiểm tra một số n có phải số nguyên tố hay không.

Input

• Vào từ thiết bị nhập chuẩn số nguyên dương \(n\) \((n \leq 10^{12})\).

Output

• Ghi ra thiết bị xuất chuẩn từ YES nếu \(n\) là số nguyên tố, NO nếu \(n\) không phải số nguyên tố.

Example

9

NO

97

YES

Trong máy tính, để tiết kiệm bộ nhớ, người ta thường tìm cách nén dữ liệu. Trong việc nén văn bản, ta sư dụng một phương pháp đơn giản đươc mô tả thông qua ví dụ sau:

Ví dụ:

Với xâu ký tự: "aaaabbb" sẽ được nén lại thành xâu "4a3b". Với xâu ký tự "aaab" sẽ được nén lại thành "3ab".

Cho một xâu \(S\) gồm các ký tự thuộc tập \('a'...'z'\). Gọt \(St\) là xâu nén của xâu \(S\) theo phương pháp được mô tả như trên. Xâu \(St\) gồm \(N\) ký tự thuộc tập các ký tự \('a'...'z'\), \('0',...'9'\)

Hãy giải nén xâu \(St\) để được xâu gốc \(S\).

Input

• Một xâu ký tự \(St\).

Output

• Một xâu ký tự \(S\) sau khi giải nén.
• Đề đảm bảo số lượng kí tự sau khi giải nén không quá \(10^{7}\).

Constraints

• \(1 \leq N \leq 10000\)

Example

2m2a3b4ezh 

mmaabbbeeeezh

Cho một khung hình chữ nhật kích thước \(A \times B\), em được phép chọn \(K\) là số nguyên bất kì từ \(10\) đến \(20\) và tiến hành xếp các mảnh hình vuông có kích thước \(K \times K\) lên khung hình \(A \times B\) với yêu cầu:

• Các cạnh của các mảnh hình vuông khi xếp cạnh phải song song với cạnh của khung hình;
• Không có hình nào thừa ra ngoài hoặc chồng lên nhau;
• Diện tích còn thừa là ít nhất.

Hãy tìm cách xếp và in ra phần diện tích còn thừa nhỏ nhất.

Input

• Dữ liệu nhập vào từ bàn phím gồm hai dòng lần lượt là hai số tự nhiên \(A, B\) (\(20 \leq A, B \leq 10^7\)).

Output

• In ra màn hình một số duy nhất là diện tích còn thừa nhỏ nhất thoả mãn yêu cầu đề bài.

Example

55
56

55

21
22

62

Cho dãy số có quy luật như sau: \(1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, \ldots\).

Cho một số tự nhiên \(N\), hãy tìm số thứ \(N\) của dãy số trên (các số được đánh thứ tự từ \(1\)).

Input

• Nhập vào số tự nhiên \(N\) \((N \leq 10^{15})\)

Output

• Ghi ra kết quả của bài toán.

Scoring

• Nếu chương trình chạy đúng những trường hợp \(N \leq 10^{6}\), thí sinh sẽ được \(60\) điểm.
• Nếu chương trình chạy đúng những trường hợp \(N \leq 10^{10}\), thí sinh sẽ được \(80\) điểm.
• Nếu chương trình chạy đúng những trường hợp \(N \leq 10^{15}\), thí sinh sẽ được \(100\) điểm.

Example

5

3

Cho dãy số \(A\) có quy luật như sau: \(1, 3, 2, 6, 4, 12, 8, 24, 16, 48, 32, 96, 64, 192, 128 \ldots\) (số ở vị trí thứ \(i\) bằng hai lần số ở vị trí thứ \(i - 2\)).

Lấy hai chữ số cuối cùng của các số của dãy số \(A\) ta được dãy số \(B\):

\(1, 3, 2, 6, 4, 12, 8, 24, 16, 48, 32, 96, 64, 92, 28 \ldots\)

Cho số tự nhiên \(N\). Tính tổng \(N\) số đầu tiên của dãy số \(B\).

Input

• Gồm một dòng chứa một số tự nhiên \(N\) \((N \leq 10^{12})\).

Output

• Gồm một dòng, chứa một số tự nhiên là kết quả của bài toán.

Scoring

• Có \(60\%\) số test ứng với \(60\%\) số điểm có: \(N \leq 100\);
• \(40\%\) số test còn lại ứng với \(40\%\) số điểm không có ràng buộc gì thêm.

Example

4

12