Từ số nguyên dương ~X~, ta có thể tạo ra số nguyên dương ~Y~ bằng cách cộng ~X~ với các chữ số của ~X~. Tức là ~Y = X +~ các chữ số của ~X~. Khi đó ~X~ và ~Y~ được gọi là cập số sinh.

Ví dụ từ số ~X = 317~ sinh ra số ~Y = 317 + 3 + 1 + 7 = 328~.

Yêu cầu

Cho số nguyên dương ~X~, hãy tìm số ~Y~.

Dữ liệu đầu vào

Gồm duy nhất một số nguyên dương ~X~ ~(10 \le X \le 1000)~.

Dữ liệu đầu ra

Gồm một số nguyên dương duy nhất là số ~Y~.

Ví dụ

Ví dụ 1

INPUT

317

OUTPUT

328

Giải thích: ~Y = 317 + 3 + 1 + 7 = 328~.

Ví dụ 2

INPUT

18

OUTPUT

27

Giải thích: ~Y = 18 + 1 + 8 = 27~.

Ở một vương quốc nọ, Quốc Vương có một chiếc rương bí mật, trong đó có ~n~ viên đá quý, viên đá quý thứ ~i~ có giá trị ~a_i~. Viên đá quý được coi là may mắn khi giá trị của nó là một số có chữ số tận cùng bằng ~9~.

Yêu cầu

Cho biết giá trị của các viên đá quý, hãy đếm xem có bao nhiêu viên đá quý may mắn.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~n~ là số lượng viên đã quý ~(1 \le n \le 1000)~.
• Dòng thứ hai chứa ~n~ số nguyên lần lượt là ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 1000\ \forall i = 1..n)~ cho biết giá trị của các viên đá quý. Các số trên một dòng được phân tách bởi khoảng trắng.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số lượng viên đá quý may mắn.

Ví dụ

Ví dụ 1

INPUT

5
192 129 68 99 251

OUTPUT

2

Giải thích: Có ~2~ viên đá quý may mắn có giá trị ~129, 99~.

Ví dụ 2

INPUT

7
31 98 239 319 996 268 959

OUTPUT

3

Giải thích: Có ~3~ viên đá quý may mắn có giá trị ~239, 319, 959~.

Có ~n~ tấm thẻ đặt thành một hàng ngang trên bàn, tấm thẻ thứ ~i~ có ghi một số có giá trị ~a_i~. Khi nhấc một tấm thẻ ra khỏi bàn, ta cần tính xem giá trị lớn nhất trong các thẻ còn lại trên bàn lớn hơn giá trị tấm thẻ nhắc ra một lượng bao nhiêu.

Ví dụ ta có ~6~ tấm thẻ trên bàn có giá trị lần lượt là ~8, 6, 7, 5, 9, 4~.

• Khi nhắc tấm thẻ thứ nhất ra khỏi bàn:

Giá trị lớn nhất trong các thẻ còn lại trên bàn là ~9~, lớn hơn giá trị tấm thẻ nhắc ra một lượng là ~9 - 8 = 1~.

• Khi nhắc tấm thẻ thứ ~5~ ra khỏi bàn:

Giá trị lớn nhất trong các thẻ còn lại trên bàn là ~8~, lớn hơn giá trị tấm thẻ nhắc ra một lượng là ~8 - 9 = -1~.

Yêu cầu

Lần lượt nhấc từng tấm thẻ (từ thẻ thứ nhất đến thẻ thứ ~n~) ra khỏi bàn, cần tính xem giá trị lớn nhất trong các thẻ còn lại trên bàn lớn hơn giá trị tấm thẻ nhấc ra một lượng bao nhiêu, sau đó đặt tấm thẻ trở lại vị trí cũ trên bàn.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~n~ là số lượng tấm thẻ ~(2 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên lần lượt là ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^6\ \forall i = 1..n)~ cho biết giá trị các tấm thẻ. Các số trên một dòng được phân tách bởi khoảng trắng.

Dữ liệu đầu ra

Gồm ~n~ số trên một dòng, số thứ ~i~ ghi kết quả khi nhấc thẻ thứ ~i~ ra khỏi bàn. Hai số kề nhau được phân tách bởi một khoảng trắng.

Ràng buộc dữ liệu

• 80% số test (ứng với 80% số điểm) có giới hạn ~2 \le n \le 10^4~.
• 20% số test (ứng với 20% số điểm) có giới hạn ~10^4 \le n \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

6
8 6 7 5 9 4

OUTPUT

1 3 2 4 -1 5

Ví dụ 2

INPUT

5
6 8 5 4 8

OUTPUT

2 0 3 4 0

Cho dãy số ~A~ gồm ~n~ số nguyên ~A_1, A_2, ..., A_n~. Một dãy con của dãy ~A~ là dãy bao gồm một số phần tử ở vị trí liên tiếp nhau trong dãy ~A~.

Ví dụ với dãy ~A~ là ~[6, 8, 3, 7]~ thì các dãy con của dãy ~A~ là: ~[6]~; ~[6, 8]~; ~[6, 8, 3]~; ~[6, 8, 3, 7]~; ~[8]~; ~[8, 3]~; ~[8, 3, 7]~; ~[3]~; ~[3, 7]~; ~[7]~.

Một số nguyên được gọi là số đặc biệt nếu tất cả các chữ số của nó là số lẻ. Ví dụ các số ~571, 555, 9393~ là các số đặc biệt, các số ~552, 868, 232~ không phải là các số đặc biệt.

Yêu cầu

Hãy tìm dãy con gồm nhiều phần tử nhất của dãy ~A~ sao cho các phần tử trong dãy con đó đều là các số đặc biệt. Đưa ra số lượng phần tử của dãy con đó.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~n~ là số lượng số trong dãy ~A~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~A_1, A_2, ..., A_n~ ~(1 \le a_i \le 10^6\ \forall i = 1..n)~ cho biết dãy ~A~. Các số trên một dòng được phân tách bởi khoảng trắng.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số lượng phần tử của dãy con liên tiếp dài nhất thỏa mãn yêu cầu đề bài.

Ràng buộc dữ liệu

• 40% số test (ứng với 40% số điểm) có giới hạn ~1 \le n \le 150~.
• 40% số test (ứng với 40% số điểm) có giới hạn ~150 \le n \le 5000~.
• 20% số test (ứng với 20% số điểm) có giới hạn ~5000 \le n \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

9
5 7 45 11 573 331 9 6 7

OUTPUT

4

Giải thích: Dãy con thỏa mãn là: ~11, 573, 331, 9~. Dãy con này có ~4~ phần tử.

Ví dụ 2

INPUT

12
6 7 5 2 5 5 8 4 1 3 2 1

OUTPUT

2

Giải thích: Có ~3~ dãy con thỏa mãn là: ~7, 5~; ~5, 5~; ~1, 3~. Tất cả đều có ~2~ phần tử.