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 \lt 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

• 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 bit của số nguyên dương \(b\) trong hệ nhị phân

Dữ liệu ra

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

Scoring

• Có \(75\)% test ứng với \(1 \le a \lt b \le 10^9\)
• Có \(25\)% test ứng với \(10^9 \lt a \lt b \le 10^{18}\)

Input 1

111
10011

Output 1

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