Mọi dữ liệu trong máy tính đều được số hóa, tức là có dạng dãy bit ~0~ hoặc ~1~. Mọi thao tác xử lý dữ liệu trên máy tính cuối cùng đều dẫn đến việc xử lý các bit. Vì vậy khi thực hiện xong tính toán, máy tính phải giải mã kết quả từ hệ nhị phân sang hệ thập phân để con người có thể hiểu và kiểm tra được. Việc đổi hệ nhị phân có dạng ~d_k d_{k-1}...d_1 d_0~ sang số thập phân thực chất chỉ là việc tính tổng ~d_k \times 2^k + d_{k-1} \times 2^{k-1} + ... + d_1 \times 2^1 + d_0 \times 2^0~.

Ví dụ: Dãy bit ~111~ trong hệ nhị phân chuyển sang hệ thập phân sẽ là số ~7~; vì ~111_2 \rightarrow 1 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 7_{10}~.

Hôm nay bạn hãy viết chương trình giải bài toán như sau: cho dãy bit của hai số nguyên dương ~a,\ b~ ~(1 < a, b \le 10^{18})~ trong hệ nhị phân.

Yêu cầu

Đếm số lượng số chính phương có trong đoạn từ ~a~ đến ~b~. Biết rằng, một số nguyên dương được gọi là số chính phương nếu căn bậc hai của nó là một số nguyên dương.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất là dãy bit của số nguyên dương ~a~ trong hệ nhị phân;
• Dòng thứ hai là dãy bít của số nguyên dương ~b~ trong hệ nhị phân.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả tìm được.

Ràng buộc dữ liệu

• Có 75% test ứng với ~1 \le a < b \le 10^9~;
• Có 25% test ứng với ~10^9 < a < b \le 10^{18}~.

Ví dụ

Ví dụ 1

INPUT

111
10011

OUTPUT

2

Giải thích:

• Số ~111~ trong hệ nhị phân là ~7~ trong hệ thập phân.
• Số ~10011~ trong hệ nhị phân là số ~19~ trong hệ thập phân. Như vậy trong đoạn từ ~7~ đến ~19~ có hai số chính phương là ~9~ và ~16~.