Cho một số nguyên dương ~N~ ~(1 \le N \le 10^{18})~. Để biến đổi số ~N~ thành số ~1~ có thể thực hiện bằng cách sử dụng các phép toán sau đây:

• Phép toán ~1~: Nếu ~N~ là số chẵn, em chia ~N~ cho ~2~;
• Phép toán ~2~: Nếu ~N~ là số lẻ, em có thể trừ đi ~1~ hoặc cộng thêm ~1~;

Yêu cầu

Em hãy viết chương trình tìm số bước ít nhất để biến đổi ~N~ về ~1~ (có thể có nhiều cách khác nhau để đạt được số bước ít nhất).

Dữ liệu đầu vào

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

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số bước ít nhất để biến đổi ~N~ thành ~1~.

Ví dụ

Ví dụ 1

INPUT

15

OUTPUT

5

Giải thích: Gồm ~5~ bước:

• ~15 \rightarrow 16~ (cộng ~1~)
• ~16 \rightarrow 8~ (chia ~2~)
• ~8 \rightarrow 4~ (chia ~2~)
• ~4 \rightarrow 2~ (chia ~2~)
• ~2 \rightarrow 1~ (chia ~2~)

Cho hai số nguyên ~S~ và ~N~ ~(1 \le S \le 100;\ 1 \le N \le 10^9)~.

Yêu cầu

Em hãy tìm số nguyên dương nhỏ nhất có đúng ~S~ chữ số và chia hết cho ~N~, nếu không có số thỏa điều kiện trên thì in ra ~-1~.

Dữ liệu đầu vào

Gồm số nguyên ~S~ và số nguyên ~N~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số nhỏ nhất thỏa yêu cầu đề bài.

Ví dụ

Ví dụ 1

INPUT

3 6

OUTPUT

102

Giải thích: Số nhỏ nhất có ~3~ chữ số mà chia hết cho ~6~ là ~102~.

Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~(3 \le N \le 10^6)~ trong đó mỗi phần tử có giá trị tuyệt đối nhỏ hơn ~10^9~.

Yêu cầu

In ra màn hình số cách chọn cặp chỉ số ~i~ và ~j~ sao cho ~1 \le i < j < N~. Các chỉ số ~i, j~ chia dãy ~A~ thành ba đoạn liên tiếp, sao cho tổng các phần tử của mỗi bằng nhau, biết rằng:

• Đoạn ~1~: các phần tử từ vị trí ~1~ đến ~i~;
• Đoạn ~2~: các phần tử từ vị trí ~i + 1~ đến ~j~;
• Đoạn ~3~: các phần tử từ vị trí ~j + 1~ đến ~N~.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa số nguyên ~N~.
• Dòng thứ hai chứa ~N~ số nguyên.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số cách chọn cặp ~(i, j)~ thoả yêu cầu đề bài.

Ví dụ

Ví dụ 1

INPUT

5
1 2 3 0 3

OUTPUT

2

Giải thích: Có ~2~ cách chọn ~(i, j)~:

• Cách ~1~: ~i = 2, j = 3~;
• Cách ~2~: ~i = 2, j = 4~.

Cho một xâu ~s~ chỉ chứa các chữ số từ 0 đến 9 và có độ dài không quá ~30~ kí tự. Ta biết rằng mỗi số từ ~1~ đến ~26~ có thể được ánh xạ thành một chữ cái từ ~A~ đến ~Z~, ví dụ như ~1 \rightarrow~ A, ~2 \rightarrow~ B, ..., ~26 \rightarrow~ Z.

Yêu cầu

Em hãy viết chương trình in ra số cách mà xâu ~s~ có thể được giải mã thành một chuỗi chữ cái hợp lệ.

Lưu ý: Nếu ký tự 0 xuất hiện riêng một mình thì xâu đó không thể được giải mã. Ví dụ: ~s =~ 01 thì kết quả là ~0~.

Dữ liệu đầu vào

Gồm xâu kí tự ~s~ chỉ chứa các kí tự từ 0 đến 9.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số cách mà xâu ~s~ có thể được giải mã thành một chuỗi chữ cái hợp lệ.

Ví dụ

Ví dụ 1

INPUT

121

OUTPUT

3

Giải thích: Với ~s =~ 121, có ~3~ cách giải mã:

• 1 2 1 ~\rightarrow~ ABA;
• 12 1 ~\rightarrow~ LA;
• 1 21 ~\rightarrow~ AU.

Ví dụ 2

INPUT

10

OUTPUT

1

Giải thích: Với ~s =~ 10, chỉ có cách duy nhất là 10 ~\rightarrow~ J.