English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/jednakos

Trong khi đọc một quyển sách toán, Mirko nhận thấy có một số đẳng thức lạ dạng A=S. Điều kì lạ là đẳng thức này không đúng (A<>S). Mirko nhận thấy rằng cần phải thêm một số dấu cộng vào giữa 1 số cặp chữ số liên tiếp ở vế trái của đẳng thức. Bạn hãy tìm cách thêm vào ít nhất các dấu cộng vào vế trái của đẳng thức để đẳng thức trở nên đúng. Các số ở đẳng thức đúng có thể có các chữ số 0 vô nghĩa ở đầu.

Input

Gồm một dòng duy nhất chứa đẳng thức dạng A=S

A và S không có chữ số 0 vô nghĩa ở đầu. A<>S

A có nhiều nhất 1000 chữ số

S<=5000

Dữ liệu liên đảm bảo có kết quả

Output

Gồm một dòng duy nhất chứa số lượng dấu cộng ít nhất cần sử dụng

Example

Input:
143175=120

Output:
2

Input:
5025=30

Output:
1

Input:
999899=125

Output:
4

---

hide comments

	smso: 2023-04-09 17:11:33 Handle cases where are lots of zeros. This would lead to TLE.
	lokesh_2052: 2021-07-12 17:05:44 lol 00000000000000000000000000000000000000000000=0 ans will 0 [Simes]: this is an invalid test case. The problem states "A and S will both be positive integers without leading zeros." Last edit: 2022-07-15 08:56:00