Time limit: 1.0s / Memory limit: 64M

Points: 100

Cho 1 số nguyên n (Với 1≤n≤1000). Tính tổng các số nguyên từ 1 đến n.

Input

Dòng đầu tiên có chứa 1 số nguyên n (Với 1≤n≤1000).

Output

Một dòng duy nhất là 1 số là tổng các số nguyên từ 1 đến n.

Simple Examples

Input

1

Output

1

Input

3

Output

6

Time limit: 1.0s / Memory limit: 64M

Points: 100

Cho 1 số nguyên n (Với 1≤n≤10). Tính n! - n giai thừa.

Input

Dòng đầu tiên có chứa 1 số nguyên n (Với 1≤n≤10).

Output

Một dòng duy nhất là 1 số là n!

Examples

Input

1

Output

1

Input

2

Output

2

Input

3

Output

6

Time limit: 1.5s / Memory limit: 64M

Points: 100

Mô tả vấn đề

Viết chương trình nhập 2 số nguyên dương, tìm ước số chung lớn nhất (gcd - greatest common divisor) và bội số chung nhỏ nhất (lcm - least common multiple)  của chúng.

Input

Nhập 2 số nguyên dương a và b (1 ≤ a, b ≤ 10~^5~)

Output

In ra ước chung lớn nhất và bội chung nhỏ nhất

Sample Input 1
2 4
Sample Output 1
2 4

Time limit: 1.0s / Memory limit: 64M

Points: 100

Giới thiệu: Đây là đề Training Python 2

Để đạt được học bổng cần xếp loại điểm rèn luyện từ mức khá trở lên. Các bạn hãy giúp Nhân và các bạn của mình kiểm tra xếp loại điểm rèn luyện của mình nhé.

Đầu vào là một số nguyên ~n~ người và các số nguyên ~a~, ~b~.

Với ~a~ là số điểm được đoàn trường đánh giá, ~b~ là số điểm thưởng đạt được.

Biết điểm rèn luyện được đánh giá như sau:

Từ ~0~ đến dưới ~30~ xếp loại Kém

Từ ~30~ đến dưới ~50~ xếp loại Yếu

Từ ~50~ đến dưới ~65~ xếp loại Trung bình

Từ ~65~ đến dưới ~80~ xếp loại Khá

Từ ~80~ đến ~100~ xếp loại Giỏi

Nếu không thuộc trường hợp nào ở trên in ra Error

Input

Dòng đầu tiên là ~n~

~n~ dòng tiếp theo là các số ~a~ ~b~ cho mỗi trường hợp

Output

~n~ dòng là đánh giá điểm rèn luyện của ~n~ bạn trên

Examples

Input

3
30 10
60 25
80 30

Output

Yếu
Giỏi
Error

Time limit: 0.1s / Memory limit: 64M

Points: 120

Giới thiệu: Đây là đề Training Python 2

Nhập vào ~2~ số nguyên ~a~ và ~b~, viết chương trình tính và in ra tổng của các số chẵn trong [a,b].

Input

~2~ dòng tương ứng với ~2~ số nguyên ~a~, ~b~

Output

Tổng các số nguyên trong đoạn [~a~, ~b~]

Examples

Input

2
4

Output

6

Time limit: 0.1s / Memory limit: 64M

Points: 100

Giới thiệu: Đây là đề Training Python 2

Viết chương trình tìm ~S~ biết:

~S = x + \frac{x^2}{2!} + \frac{x^3}{3!}+ ... + \frac{x^n}{n!}~

Input

2 dòng: lần lượt là ~x~ và ~n~

Output

Giá trị ~S~ mà bạn tính được làm tròn tới chữ số thập phân thứ ~2~

Examples

Input

2 
2

Output

4.00

Time limit: 1.0s / Memory limit: 64M

Points: 100

Giới thiệu: Đây là đề Training Python

Tính tổng các chữ số của số nguyên dương trong hệ thập phân.

Input

Dòng đầu ghi số nguyên dương TT là số bộ test; TT dòng tiếp theo, mỗi dòng chứa một số nguyên dương nn ghi ở hệ thập phân.

Output

Với mỗi bộ test, ghi ra trên một dòng một số là tổng các chữ số của số nn tương ứng.

Examples

Input

2
13
256

Output

4
13

Time limit: 1.0s / Memory limit: 64M

Points: 100

Giới thiệu: Đây là đề Training Python 2

Hai anh em nhà N đang tập làm phép chia và đếm số, người anh chỉ thích những số chia hết cho 3. Người em chỉ thích những số chia hết cho 5. Hãy giúp anh em họ in ra các số từ 1 đến n. Nhưng đối với bội số của 3 thì in ra "Anh" và cho bội số của 5 thì in ra 'Em" thay vì in số hiện tại. Đối với các số là bội số của cả 3 và 5 thì in "AnhEm".

Input

Số nguyên dương N

Output

n dòng tương ứng với các giá trị theo ràng buộc đề bài

Examples

Input

3

Output

1
2
Anh

Time limit: 1.0s / Memory limit: 64M

Points: 100

Giới thiệu: Đây là đề Training Python 2

Bảo Bảo có ~x~ viên sỏi trên bàn. Mỗi viên có thể có màu đỏ ~R~, xanh lá cây ~?~ và xanh lục ~?~. Bảo Bảo muốn đếm số lượng viên sỏi tối thiểu để lấy từ bàn sao cho hai viên sỏi lân cận bất kì có màu sắc khác nhau. Các viên sỏi trong một hàng được coi là lân cận nếu không có các viên sỏi nào khác giữa chúng.

Input

dòng ~1~: số nguyên ~x~,~(1≤x≤50)~ - số lượng viên sỏi trên bàn.

dòng ~2~: chứa chuỗi ~?~ - đại diện cho màu sắc của viên sỏi

Output

Là một số nguyên - trả lời cho câu hỏi trên

Examples

Input

6
RGBBGG

Output

2

Time limit: 1.0s / Memory limit: 64M

Points: 100

Giới thiệu: Đây là đề Training Python 2

Số hoàn hảo (số hoàn thiện) là một số nguyên dương mà tổng các ước nguyên dương của nó (không bao gồm ước lớn nhất) bằng chính nó.

Ví dụ:

~6 = 1 + 2 + 3~ một số hoàn hảo.

Nhiệm vụ của bạn là viết chương trình kiểm tra ~1~ số nguyên nhập từ bàn phím có phải số hoàn hảo hay không!

Input

Số nguyên dương ~N~

Output

In ra ~YES~ nếu ~n~ là số hoàn hảo

In ra ~NO~ nếu ~n~ không phải số hoàn hảo

Examples

Input

6

Output

YES

Time limit: 1.0s / Memory limit: 64M

Points: 100

Giới thiệu: Đây là đề Training Python 2

Cho số nguyên ~n~ .Vẽ hình vuông đặc bằng dấu "*" có độ dài cạnh ~n~.

Input

Dòng duy nhất chứa số nguyên dương ~n~ ~(2 \le n \le 100)~

Output

In ra hình vuông đặc như ví dụ dưới đây.

Examples

Input

3

Output

***
***
***

Time limit: 1.0s / Memory limit: 64M

Points: 100

Giới thiệu: Đây là đề Training Python 2

Viết chương trình liệt kê các ước nguyên dương của số nguyên ~n~ nhập từ bàn phím theo thứ tự giảm dần.

Input

Một dòng duy nhất là số nguyên ~n~ ~(n \ge 0)~

Output

Danh sách các ước số nguyên dương của số ~n~ theo thứ tự giảm dần, các số cách nhau bởi ~1~ dấu cách. Nếu số ~n~ có vô số ước nguyên dương, in ra INF

Examples

Input

8

Output

8 4 2 1

Time limit: 2.3s / Memory limit: 196M

Points: 120

Giới thiệu: Đây là trò chơi có thật trong đợt huấn lệnh vừa rồi

Gần đây, thầy Nguyễn Hữu Tình đã mời anh Phạm Văn Hạnh (HCV Olympic Tin học Quốc tế) về dạy cho đội tuyển tin học của IUH, sau khóa học thì anh Hạnh có tổ chức một trò chơi đó là đếm số từ 1 đến vô cùng đến khi có một người sai luật thì sẽ kết thúc, luật chơi như sau:

Nếu đến lượt bạn mà là một con số chia hết cho 3 hoặc trong số đó có chữ số 3 thì bạn phải vỗ tay, còn không thì sẽ hô to số đó.

Mọi người không muốn thua quá sớm trong trò chơi này nên đã nhờ bạn code một phần mền để kiểm tra xem số đó có chia hết cho 3 hoặc các chữ số trong đó có chữ số 3 hay không? Bạn hãy giúp mọi người nhé!

Ảnh

Input

Nhập một số nguyên n ~(0≤ n ≤10^{10000000})~.

Output

Nếu n là con số chia hết cho 3 hoặc có chữ số là 3 thì in YES, nếu không thì in NO

Examples

Input

10

Output

NO

Input

13

Output

YES

Input

6

Output

YES

Hint: Chú ý tối ưu code