Bài tập

Bạn An đang chuẩn bị đi chơi tuy nhiên bạn sợ việc sử dụng tiền tài khoản đôi khi bị nghẽn mạng sẽ không chuyển được tiền đi xe, tiền mua các nhu yếu phẩm, mua quà, ... nên bạn nhờ cửa hàng B đổi cho mình \(n\) nghìn đồng tiền tài khoản thành tiền mặt. Để tiện cầm tiền mặt, bạn An nhờ cửa hàng B đổi tiền cho mình sao cho số tờ là nhỏ nhất có thể. Em hãy giúp cửa hàng B thực hiện công việc trên, biến rằng tiền Việt Nam có các mệnh giá : 1 nghìn đồng, 2 nghìn đồng, 5 nghìn đồng, 10 nghìn đồng, 20 nghìn đồng, 50 nghìn đồng, 100 nghìn đồng, 200 nghìn đồng, 500 nghìn đồng.

Input

Đọc từ tệp DT.INP gồm một số nguyên dương duy nhất \(n\) (\(n \le 10^9\)).

Output

Ghi vào tệp DT.OUT ghi theo cấu trúc sau :

Các dòng đầu trên mỗi dòng kê mệnh giá và số tờ tiền mặt : mệnh giá trước, số tờ sau (đặt cách nhau một dấu cách trống, các mệnh giá không có tờ nào thì không kê).

Dòng cuối cùng ghi tổng số tờ.

Example

1234

500 2
200 1
20 1
10 1
2 2
7

Xâu đối xứng là xâu đọc từ trái qua phải giống như xâu đọc từ phải qua trái.

Ví dụ: Các xâu ABA, ABCCBA là các xâu đối xứng.

Bạn có được phép thuật lấy một ký tự bất kỳ để biến đổi thành một ký tự khác và cho phép sắp xếp thứ tự các ký tự trong xâu.

Ví dụ: Cho xâu \(S=\)ABCB có thể biến đổi thành xâu \(S=\)ABAB và có thể sắp xếp thành xâu \(S=\)ABBA. Xâu cuối cùng nhận được là xâu đối xứng.

Yêu cầu: Cho xâu \(S\) chỉ gồm ba loại ký tự A,B,C, bạn có thể thực hiện phép thuật ít nhất để biến đổi thành xâu đối xứng.

Input

Một xâu ký tự \(S\) chỉ gồm ba loại ký tự A,B,C có độ dài không quá 1 000 ký tự.

Output

In ra một số tự nhiện là số lần thực hiện phép thuật ít nhất để biến đổi xây \(S\) thành xâu đối xứng.

Example

CCB

0

AAABBCB

1

Thám tử K cho phép chuỗi nhị phân có cặp \(00\) xuất hiện, nhưng chỉ không quá 2 lần. Hãy sử dụng đệ quy để liệt kê tất cả các chuỗi nhị phân có độ dài \(N\) thỏa mãn ràng buộc về số lần xuất hiện của cặp "00".

Input

Một số nguyên dương \(N\) (\(1 \leq N \leq 15\)).

Output

In ra số lượng chuỗi nhị phân thỏa mãn điều kiện.

Example

1

2

2

4

3

8

4

15

Xây dựng hàm giaithua(n) để tính giai thừa của một số nguyên không âm \(n\). Giá trị trả về là \(n!\). Áp dụng hàm đã xây dựng để tính và in ra \(n!\) với \(n\) được nhập từ bàn phím.

\(n! = 1 \times 2 \times 3 \times \dots \times n\).

Input

• Một số nguyên không âm \(n\) (\(0 \leq n \leq 15\)).

Output

Một dòng duy nhất chứa giá trị của \(n!\).

Example

3

3! = 6