Cho một số nguyên dương ~N~ có 4 chữ số.

Yêu cầu: Hãy sắp xếp lại các chữ số của ~N~ để được số lớn nhất mà chia hết cho 5, nếu không tìm được số chia hết cho 5 thì ghi ra  - 1.

Input

• Gồm một số nguyên dương ~N~ có 4 chữ số.

Output

• Gồm một số duy nhất là kết quả của bài toán.

Example

Input

2014

Output

4210

Cho số nguyên dương ~n~ và dãy số nguyên dương gồm ~n~ phần tử ~a_1,a_2,…,a_n~.

Yêu cầu: Hãy đưa ra số lượng ước dương của một phần tử có nhiều ước dương nhất trong dãy số đã cho.

Input

• Dòng 1 chứa số nguyên dương ~n~ (~1≤n≤10^5~).
• Dòng 2 chứa ~n~ số nguyên là giá trị của các phần tử từ ~a_1,a_2,…,a_n~ (~1≤a_i≤10^6~)

Output

Ghi ra một số nguyên là kết quả bài toán — số lượng ước dương lớn nhất của một phần tử trong dãy số.

Scoring

• Có 70% số test ứng với 70% số điểm thỏa mãn: ~n≤10^3~ và ~a_i≤10^3~;
• Có 15% số test ứng với 15% số điểm thỏa mãn: ~n≤10^3~ và ~a_i≤10^6~;
• Có 15% số test còn lại ứng với 15% số điểm không có ràng buộc gì thêm.

Examples

Input

4
3 8 16 22

Output

5

Input

5
3 5 6 17 8

Output

4

Note

• Phần tử 16 có nhiều ước dương nhất là 1,2,4,8,16 (tổng cộng 5 ước).

Cho một số nguyên dương N có số lượng chữ số không vượt quá ~10^5~.

Yêu cầu: Hãy viết chương trình hoán vị các chữ số của ~N~, sao cho sau khi hoán vị ta thu được một số nguyên dương lớn nhất là bội của số ~30~.

Input

Gồm một số nguyên dương N.

Output

• Gồm một số nguyên dương là kết quả của bài toán (trong trường hợp không tìm được ghi số -1).

Examples

Input

102

Output

210

Input2

106

Output2

-1

Note

• Ở ví dụ 1, số ~210~ là bội lớn nhất sau khi hoán đổi từ số ~102~ .

Cho một dãy gồm ~n~ số nguyên dương.

Yêu cầu: Xác định số cách chọn hai phần tử trong dãy số sao cho tổng hai phần tử này có giá trị chẵn.

Input

• Dòng thứ nhất ghi số nguyên dương ~n~ (~1≤n≤10^5~).

• Dòng thứ hai ghi ~n~ số nguyên dương ~a_i~ (~1≤a_i≤10^3~).

Output

• Một số là kết quả tìm được.

Examples

Input1

5
2 7 1 4 2

Output1

4

Input2

5
2 4 7 8 6

Output2

6

Note

• Giải thích ví dụ 1: Các cặp số được chọn là (2;4),(2;2),(4;2),(7;1).

• Giải thích ví dụ 2: Các cặp số được chọn là (2;4),(2;8),(2;6),(4;8),(4;6),(8;6).