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

Cho mảng số nguyên ~A~ có ~n~ phần tử được nhập từ bàn phím. Hãy viết chương trình tìm ~3~ phần tử ở các vị trí khác nhau trong mảng sao cho tích của ~3~ phần tử đó là lớn nhất. Sau đó, hãy in giá trị tích lớn nhất mà bạn tìm được lên màn hình.

Input

Dòng ~1~ là số lượng phần tử của mảng ~n~. Dòng tiếp theo là ~n~ số nguyên tương ứng là các phần tử của mảng.

Output

Tích lớn nhất mà bạn tìm được.

Examples

Input

5
1 2 3 4 5

Output

60

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

Cho mảng số nguyên ~A~ có ~n~ phần tử, hãy tìm ~2~ phần tử lân cận trong mảng sao cho tổng của chúng là lớn nhất. Giả sử phần tử cuối cùng và phần tử đầu tiên cũng có tính lân cận (tạo thành vòng tròn khép kín)

Input

Cho mảng số nguyên ~A~ có ~n~ phần tử, hãy tìm ~2~ phần tử lân cận trong mảng sao cho tổng của chúng là lớn nhất. Giả sử phần tử cuối cùng và phần tử đầu tiên cũng có tính lân cận (tạo thành vòng tròn khép kín)

Output

In ra ~2~ phần tử lân cận nhau (cách nhau bởi ~1~ dấu cách) thỏa mãn yêu cầu đề bài.

Examples 1

Input

5
3 2 -1 2 4

Output

4 3

Examples 2

Input

6
1 2 6 1 6 2

Output

6 2

Note

Giữ nguyên thứ tự ban đầu của chúng

Nếu có nhiều kết quả, in ra kết quả ở cặp có chỉ số mảng (của phần tử đầu tiên) lớn hơn.

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

Số nguyên tố hay còn gọi là hợp số, đây là tập hợp số tự nhiên chỉ chia hết cho ~1~ và chính nó. Nhập vào một số nguyên dương ~N~, hãy phân tích số ~N~ thành tích các thừa số nguyên tố

Input

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

Output

~1~ dòng duy nhất là tích của các thừa số nguyên tố (các thừa số theo thứ tự từ bé đến lớn). Nếu không có thừa số in ra rỗng " " (không có dấu ngoặc kép)

Examples

Input

456

Output

2*2*2*3*19

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

Hôm nay, Nhi lên H2.2 chơi thì phát hiện trên bàn có một chuỗi ~t~. Nhi đặc biệt thích kí tự '~n~'. Nhi gọi một chuỗi là đặc biệt nếu chuỗi đó có đúng hơn ~1~ nửa số ký tự trong chuỗi là kí tự '~n~'. Ví dụ "~nnnbb~" hoặc "~nann~" là một chuỗi đặc biệt tuy nhiên chuỗi '~lnln~' hoặc chuỗi rỗng thì không phải chuỗi đặc biệt.

Nhi quyết định xóa một vài kí tự ra khỏi chuỗi. Nhi muốn biết sau khi xóa một số kí tự (có thể là không xóa kí tự nào) để có được chuỗi đặc biệt thì chuỗi còn bao nhiêu kí tự.

Input

Dòng duy nhất chứa chuỗi ~t~, ~1 \le t \le 50~ gồm các kí tự tiếng anh viết thường (nghĩa là không có ă, ấ, ơ, ....) luôn đảm bảo rằng có kí tự 'n' trong chuỗi ~t~ (nếu không có kí tự 'n' in ra -1).

Output

In ra 1 số nguyên duy nhất là độ dài của chuỗi đặc biệt dài nhất mà Nhi có được sau khi xóa một vài kí tự khỏi chuỗi t

Examples 1

Input

anaaaan

Output

3

Examples 2

Input

nnnbnn

Output

6

Đây là đề Training Python 3

Ở vương quốc BULCIA mọi người rất thích những con số may mắn (những con số mà chúng chỉ chứa số ~4~ và số ~7~). Ví dụ, số ~47~, ~477~, ~74~ là những số may mắn và ~5~, ~467~, ~17~ không phải là những con số may mắn.

Và họ gọi một số là suýt may mắn nếu nó có thể chia hết cho một số may mắn. Hãy giúp người dân BULCIA kiểm tra xem số tự nhiên ~n~ có phải là số suýt may mắn không?

Input

~1~ dòng duy nhất một số tự nhiên ~n~ ~(1 \le n \le 1000)~

Output

Trong dòng duy nhất in YES, nếu số ~n~ là số may mắn hoặc là số suýt may mắn. Nếu không, hãy in NO.

Examples 1

Input

47

Output

YES

Examples 2

Input

16

Output

YES

Examples 3

Input

78

Output

NO

Đây là đề Training Python 3

Tuần làm việc của bạn gồm ~n~ ngày được đánh số từ ~1~ tới ~n~, sau ngày thứ ~n~ thì sẽ là ngày thứ ~1~ và tương tự. Và ~3~ ngày trong tuần sẽ là ngày nghỉ (zè ze :D). Một ngày nghỉ là ngày thứ ~n~, ngày cuối cùng trong tuần. Nhiệm vụ của bạn là chọn ~2~ ngày nghỉ còn lại, sao cho:

• Không có ~2~ ngày nghỉ nào kề nhau. Có nghĩa là bạn không thể chọn ngày ~1~ là ngày nghỉ vì ngày ~1~ là ngày tiếp theo của ngày ~n~.

• Bạn cần chia các ngày nghỉ sao cho tối ưu nhất có thể, có nghĩa là, nếu chia ngày nghỉ ra làm ~3~ đoạn có độ dài ~a1~, ~a2~, ~a3~, thì ta cần tối ưu sao cho ~min(|a1 - a2|, |a2 - a3|, |a3 - a1|)~ là lớn nhất

Input

Dòng đầu tiên chứa ~1~ số t duy nhất ~(1 \le t \le 1000)~ - số lượng test cases.

~t~ dòng tiếp theo mỗi dòng chứa ~1~ số nguyên n duy nhất ~n~ ~(6 \le n \le 10^9)~

Output

Đối với mỗi test case, output là ~1~ số nguyên - giá trị ~min(|a1 - a2|, |a2 - l3|, |a3 - a1|)~ là lớn nhất

Examples

Input

3
6
10
1033

Output

0
1
342

Note

Hình dưới đây mô tả ~2~ test case. Ngày nghỉ được đánh dấu màu tím, ngày nghỉ mặc định được đánh dấu màu đỏ, khoảng thời gian làm việc được gạch chân màu xanh lá cây.

• Trong testcase ~1~, có duy nhất một cách chọn ngày nghỉ đó là chọn ngày ~2~, ~3~ và ~4~( vì ngày ~1~ và ngày ~5~ là những ngày nằm bên cạnh ngày ~n~). Vì vậy chỉ có duy nhất ~1~ cách chọn những ngày nghỉ mà không bị liền kề nhau, đó là chọn ngày ~2~ và ngày 4. ~a1~ = ~a2~ = ~a3~ = 1, đáp án ~min(|a1 − a2|,|a2 - l3|, |a3 - a1|)~=0.

• Trong test case ~2~, một trong những cách chọn được trình bày dưới đây, ta có thể chọn ngày ~3~ và ngày ~5~ là ngày nghỉ.

Vậy đáp án tối ưu theo yêu cầu của đề bài sẽ là ~1~ = ~min (1,3,2)~ = ~min (| 2 − 1 |, | 1 − 4 |, | 4 − 2 |)~. Có thể chỉ ra được rằng không thể có cách chọn ngày nghỉ nào có thể cho ra đáp án lớn hơn.

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

Nam hay sử dụng mạng xã hội để giết thời gian. Trong trang danh sách trò chuyện, khi Nam gửi tin nhắn đến một người bạn nào đó, thì cuộc trò chuyện của người bạn đó sẽ xuất hiện ở đầu trang. Thứ tự đối với các cuộc trò chuyện khác không thay đổi. Trong trường hợp nếu không có cuộc trò chuyện nào với người bạn này trước đó, thì cuộc trò chuyện mới sẽ được chèn vào đầu danh sách trò chuyện.

Giả sử rằng Nam chưa có cuộc trò chuyện nào trước đó, và Nam tạo một danh sách các cuộc trò chuyện sau khi tất cả các tin nhắn của anh ấy đã được gửi đi thành công. Giả sử không có người bạn nào nhắn bất kì tin nhắn nào cho Nam.

Input

Dòng đầu tiên chứa 1 số ~n~ ~(1 \le n \le 200 000)~ - số tin nhắn mà Nam gửi.

~n~ dòng tiếp theo hiển thị người nhận tin nhắn được sắp xếp theo thứ tự tin nhắn được gửi. Tên của mỗi người tham gia cuộc trò chuyện là một dãy kí tự gồm các chữ cái tiếng Anh viết thường có độ dài tối đa là ~10~ kí tự.

Output

In tất cả những người mà Nam đã nói chuyện theo thứ tự các cuộc trò chuyện từ trên xuống dưới.

Examples 1

Input

4
alex
ivan
roman
ivan

Output

ivan
roman
alex

Examples 2

Input

8
alina
maria
ekaterina
darya
darya
ekaterina
maria
alina

Output

alina
maria
ekaterina
darya

Note

Trong test case 1, Nam gửi tin nhắn cho bạn có tên "alex", danh sách chat của Nam sẽ hiển thị như sau:

1. alex

Sau đó Nam gửi tin nhắn cho bạn "ivan", danh sách chat của Nam sẽ hiển thị như sau:

1. ivan
2. alex

Nam gửi tin nhắn thứ 3 cho người bạn tên "roman", danh sách trò chuyện của Nam sẽ được hiển thị như sau:

1. roman
2. ivan
3. alex

Nam viết tin nhắn thứ tư cho bạn bè bằng tên "ivan", cho người mà anh ta đã gửi tin nhắn, vì vậy danh sách các cuộc trò chuyện thay đổi như sau:

1. ivan
2. roman
3. alex