Cho 1 số nguyên dương a (Với 1≤a≤1000). Hãy xuất ra số nguyên a đó.

Input

Số nguyên dương a (Với 1≤a≤1000).

**Output**

Một dòng duy nhất là số nguyên dương a đã cho.

Simple Input

1

Simple Output

1

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

Cho 1 số nguyên n (Với 1≤n≤10000). Tính tổng n số nguyên dương không lẻ đầu tiên.

Input

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

Output

Một dòng duy nhất là 1 số là tổng n số nguyên dương không lẻ đầu tiên.

Examples

Input

1

Output

2

Input

3

Output

12

Input

9

Output

90

Viết chương trình tính giai thừa n!

Input Input một dòng duy nhất số nguyên n (n≤15)

Output
Output một dòng duy nhất giá trị giai thừa của số nguyên n

Examples

Input

4

Output

24 

Viết chương trình in ra màn hình tất cả các ước số của 1 số nguyên n nhập từ bàn phím.

Input

Input một dòng duy nhất số nguyên n (n≤100000)

Output

Output tất cả ước số của số nguyên n. Mỗi ước số được in trên một dòng

Examples

Input

6

Output

1
2
3
6

Cho 1 số nguyên n (Với 1≤n≤10000). Kiểm tra xem số n có phải số nguyên tố hay không ? Biết số nguyên tố là số chỉ có 2 ước.

Ví dụ:

1 không phải số nguyên tố vì nó chỉ có 1 ước (1).

4 không phải số nguyên tố vì nó chỉ có 3 ước (1,2,4).

7 là phải số nguyên tố vì nó chỉ có 2 ước (1,7).

Input

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

Output

Một dòng duy nhất chứa "YES" nếu n là số nguyên tố. Nếu n không là số nguyên tố thì chứa "NO".

Examples

Input

1

Output

NO

Input

3

Output

YES

Cho 2 số nguyên n, x (Với 0≤x≤9, 1≤n≤10000). Tính số lượng chữ số x trong chữ số n.

Input

Dòng đầu tiên chứa 2 số nguyên n, x (Với 0≤x≤9, 1≤n≤~10^{18}~).

Output

Một dòng duy nhất chứa số lượng chữ số x trong chữ số n.

Examples

Input

3 0

Output

0

Input

19 9

Output

1

Input

1111 1

Output

4

Cho 2 số nguyên l, r (Với 1≤l≤r≤10000). Tính số lượng chữ số 1 trong các số thuộc đoạn từ l đến r (Cụ thể là tính tổng chữ số 1 trong từng chữ số l,l+1,l+2,...,r−1,r) .

Input

Dòng đầu tiên chứa 2 số nguyên l, r (Với 1≤l≤r≤10000).

Output

Một dòng duy nhất chứa số lượng chữ số 1 trong các số thuộc đoạn từ l đến r.

Examples

Input

19 21

Output

2

Input

44 46

Output

0

Cho 1 số nguyên n (Với 1≤n≤25). Tính số Fibonacci thứ n. Biết số Fibonacci - https://vi.wikipedia.org/wiki/Dãy_Fibonacci - là số mà số sau bằng tổng 2 số trước. Bắt đầu với số thứ 1 là 1 và số thứ 2 cũng là 1.

Input

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

Output

Một dòng duy nhất là 1 số là số Fibonacci thứ n.

Examples

Input

1

Output

1

Input

2

Output

1

Input

3

Output

2

Input

4

Output

3

Ngày xửa ngày xưa, trong một vương quốc nọ có một cô công chúa xinh đẹp. Kluco muốn lấy cô công chúa xinh đẹp đó chỉ khi anh ấy trả lời được câu hỏi của nhà vua. Nhà vua cho anh ấy một số nguyên ~n~ và yêu cầu anh ấy viết ra số đảo ngược của nó. Là một lập trình viên tài ba, bạn hãy giúp Kluco lấy được cô công chúa xinh đẹp nhé!

Nhiệm vụ của bạn là viết chương trình mô phỏng chiếc gương thần kỳ này.

Input

• Một số nguyên dương ~n~ (~1 \leq n \leq 10^9~).

Output

• Số nguyên là kết quả khi viết ~n~ lên gương thần kỳ.

Sample Input 1

1234

Sample Output 1

4321

Sample Input 2

790

Sample Output 2

97

Cho 1 số nguyên dương n (Với 1≤n≤10000). Xuất ra bàn cờ vua có kích thước nxn - n dòng và n cột. Quân đen thì in ra 1 còn quân trăng thì in ra 0. Và ô cờ đầu tiên ở gốc trái trên có màu trắng.

Input Dòng đầu tiên là chứa 2 số nguyên dương n, n (Với 1≤n≤10000)

Output

In ra nhiều dòng là bàn cờ vua với ô đen là số 1 và ô trắng là sô 0.

Simple Examples

Input

1

Output

0

Input

3

Output

010
101
010

Input

9

Output

010101010
101010101
010101010
101010101
010101010
101010101
010101010
101010101
010101010

Trong một ngôi làng nhỏ, có một số nguyên ~n~ luôn khát khao trở thành giống số nguyên ~m~. Bạn của n là hai số 2 và 3. Một ngày nọ, ~n~ tâm sự về ước mơ của mình. Nghe xong câu chuyện, số 2 và số 3 cảm động và ngỏ lời với ~n~: "Hãy kết hợp với chúng tôi, biết đâu bạn có thể trở thành ~m~ bằng cách nhân với 2 hoặc 3."

Bạn hãy thử tính xem, khi ~n~ được nhân với 2 hoặc 3, nó có thể trở thành ~m~ hay không nhé!

Input

Hai số nguyên ~n~ và ~m~ ~(1 \le n, m \le 10^{18})~.

Output

In ra số lần kết hợp của ~n~ với số 2 và 3 để trở thành ~m~. Nếu không thể, in ra −1.

Sample Input

120 51840

Sample Output

7

Giải thích

Trong ví dụ trên N có thể di chuyển như sau:

~(120 → 240 → 720 → 1440 → 4320 → 12960 → 25920 → 51840)~.

Lưu ý : Nếu trình chấm phát hiện AI sẽ bị BAN.

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

hpgiakhang1405 là một người thích sự hoàn hảo (có lẽ thế :v). Vì thế khi anh ấy thấy một con số không hoàn hảo thì trong ngày hôm ấy anh ấy sẽ không có mood làm gì cả. Bạn hãy xem rằng trong ngày hôm nay anh ấy có bị tụt mood không nhé.

Một số hoàn hảo được định nghĩa là tổng các ước của nó (ngoại trừ chính nó) bằng chính số đó.

Ví dụ:

• 6 = 1 + 2 + 3.

Hãy viết chương trình kiểm tra một số nguyên dương ~n~ (~1 \leq n \leq 10^6~) có phải là số hoàn hảo hay không.

Input

• Một số nguyên dương ~n~.

Output

• In ra "YES" nếu ~n~ là số hoàn hảo.
• In ra "NO" nếu không phải.

Sample Input 1

6

Sample Output 1

YES

Sample Input 1

12

Sample Output 1

NO