~T~ là tổng các chữ số của ~N~. Số ~N~ được gọi là số đẹp nếu hàng đơn vị của ~T~ là số ~9~. Ví dụ số ~18~ là số đẹp vì có ~T = 1 + 8 = 9~.

Cho một số ~N~, hỏi ~N~ có phải là số đẹp hay không?

Input

Từ tệp văn bản SODEP.INP chứa một số tự nhiên ~N~ duy nhất (~0 \leq N \leq 10^9~).

Output

Đưa ra tệp SODEP.OUT số 1 nếu ~N~ là số đẹp, ngược lại ghi số 0.

Sample Input 1

27

Sample Output 1

1

Sample Input 2

111

Sample Output 2

0

Một chuỗi kí tự thuần nhất được định nghĩa là chuỗi chỉ bao gồm các kí tự latinh in hoa từ ~'A'~ đến ~'Z'~. Chuỗi kí tự thuần nhất có thể được thu gọn thành các kí tự kèm theo số lần xuất hiện liên tiếp của kí tự đó (Số lần xuất hiện sẽ đứng ngay trước kí tự, nếu số lần xuất hiện là ~1~ thì không cần ghi số ~1~). Ví dụ: Chuỗi thuần nhất ~AABBCCCDDEAAA~ được thu gọn thành chuỗi ~2A2B3C2DE3A~.

Yêu cầu: Đọc các chuỗi thuần nhất từ tệp dữ liệu THUGON.INP có độ dài không quá ~255~ kí tự và chuyển thành chuỗi thu gọn.

Input

Từ tệp văn bản THUGON.INP gồm nhiều dòng, mỗi dòng là một chuỗi thuần nhất.

Output

Đưa ra tệp văn bản THUGON.OUT gồm nhiều dòng, mỗi dòng tương ứng là chuỗi thu gọn thỏa mãn yêu cầu đề bài.

Sample Input 1

AABBCCCDDEAAA
ABBBBBDDEE

Sample Output 1

2A2B3C2DE3A
A5B2D2E

Nhân dịp kỷ niệm ngày Quốc tế Phụ nữ 8/3, Đoàn trường X dự định tổ chức cho các em học sinh nữ trong toàn trường thi trình diễn áo dài. Các em học sinh nữ được chia thành ~N~ nhóm, nhóm thứ ~i~ gồm ~S_i~ người (~1 \leq S_i \leq 4~) và mỗi lượt trình diễn chỉ được biểu diễn tối đa ~4~ người. Hỏi đoàn trường X cần tổ chức ít nhất bao nhiêu lượt trình diễn để tất cả các học sinh nữ đều được biểu diễn phần thi áo dài của mình, với điều kiện các em trong cùng một nhóm phải trình diễn áo dài cùng một lượt (Một lượt biểu diễn có thể có một hoặc nhiều nhóm cùng biểu diễn).

Yêu cầu: Hãy xác định số lượt trình diễn tối thiểu để tất cả các em học sinh nữ tham gia phần thi của mình.

Input

Đọc từ file AODAI.INP gồm 2 dòng:

• Dòng thứ nhất gồm một số nguyên dương ~N~ (~1 \leq N \leq 10^3~).

• Dòng thứ hai gồm ~N~ số nguyên dương ~S_1, S_2, ..., S_N~ (~1 \leq S_i \leq 4~).

Output

Ghi ra file AODAI.OUT một số nguyên dương duy nhất là đáp án đề bài yêu cầu.

Sample Input 1

4
4 3 2 1

Sample Output 1

3

Sample Input 2

6
4 1 2 3 2 3

Sample Output 2

4

Notes

Trong ví dụ thứ nhất ta có thể chia ra 3 lượt trình diễn với cách xếp như sau:

• ~\{1, 2\}, \{3\}, \{4\}~

• ~\{1, 3\}, \{2\}, \{4\}~

Trong ví dụ thứ hai ta có thể chia ra 4 lượt trình diễn với cách xếp như sau:

• ~\{1, 3\}, \{2, 2\}, \{3\}, \{4\}~

Bờm đang học về số học, cậu rất yêu thích những con số có tính chất đặc biệt. Số đặc biệt là số có đúng ~3~ ước nguyên dương.

Yêu cầu: Cho ~N~ số nguyên dương lần lượt là ~a_1, a_2, \cdots, a_N~ (~1 \leq a_i \leq 10^9~). Với mỗi số ~a_i~, cần xác định số đặc biệt ~b_i~ nhỏ nhất không nhỏ hơn ~a_i~.

Input

Dữ liệu vào: Từ tệp văn bản SDB.INP gồm ~2~ dòng.

• Dòng thứ nhất chứa một số ~N~ (~1 \leq N \leq 10^6~).

• Dòng thứ hai gồm ~N~ số nguyên ~a_1, a_2, \cdots, a_N~ (~1 \leq a_i \leq 10^9~).

Output

Kết quả: Đưa ra tệp văn bản SDB.OUT gồm ~N~ số nguyên ~b_1, b_2, \cdots, b_N~ thỏa mãn yêu cầu đề bài.

Sample Input 1

3
6 3 20

Sample Output 1

9 4 25

Sample Input 2

5
1 10 5 100 7

Sample Output 2

4 25 9 121 9

Notes

Ở test ví dụ thứ nhất:

• ~9~ là số nhỏ nhất không nhỏ hơn ~6~ có 3 ước nguyên dương là ~1, 3, 9~.

• ~4~ là số nhỏ nhất không nhỏ hơn ~3~ có 3 ước nguyên dương là ~1, 2, 4~.

• ~25~ là số nhỏ nhất không nhỏ hơn ~20~ có 3 ước nguyên dương là ~1, 5, 25~.

Bình là học sinh có đam mê với các con số. Một hôm Bình ngồi viết ra 1 dãy số nguyên bất kì và nhận thấy có nhiều số nguyên có giá trị bằng nhau. Bình muốn biết dãy số vừa viết ra có bao nhiêu cặp số có giá trị bằng nhau nên nhờ các bạn học sinh giỏi Tin lập trình giúp.

Yêu cầu: Cho ~N~ số nguyên dương lần lượt là ~a_1~, ~a_2~, ..., ~a_N~. Hãy giúp Bình xác định có bao nhiêu cặp số bằng nhau (~a_i = a_j~ với ~i < j~ được tính là ~1~ cặp).

Input

Từ tệp văn bản CSBN.INP gồm ~2~ dòng:

• Dòng thứ nhất là số nguyên ~N~ (~1 \le N \le 10^7~).

• Dòng thứ hai gồm ~N~ số ~a_1~, ~a_2~, ..., ~a_N~ (~1 \le a_i \le 10^9~).

Output

Đưa tệp văn bản CSBN.OUT chứa số cặp bằng nhau.

Sample Input 1

5
4 5 4 6 1

Sample Output 1

1

Sample Input 2

7
7 8 6 8 6 3 6

Sample Output 2

4