Định đề Bertran:

"Với mọi số nguyên ~n \ge 2~ bao giờ cũng tìm thấy số nguyên tố ~p~ thỏa mãn ~n < p < 2n~."

Định đề này do nhà toán học Pháp Joseph Bertran đưa ra năm 1845 sau khi đã kiểm tra với mọi ~n \le 3000000~. Điều này đã được Tchebušep chứng minh năm 1850. Năm 1932 Erdoes đã tìm được cách chứng minh mới đơn giản hơn.

Nhiệm vụ của bạn rộng hơn một chút: với ~n~ cho trước, hãy xác định số lượng số nguyên tố ~p~ thỏa mãn điều kiện ~n < p < 2n~.

Input

Chứa số nguyên dương ~n~ (~1 \le n \le 10^7~).

Output

In ra một số nguyên duy nhất là số lượng số nguyên tố ~p~ thỏa mãn ~n < p < 2n~.

Examples

Input 1

239

Output 1

39

Input 2

3000

Output 2

353

Trong bài toán này, chúng ta quan tâm đến tổng các ước số chặt của một số tự nhiên. Các ước số chặt của một số tự nhiên ~N~ là các số ~K~ nhỏ hơn hẳn ~N~, sao cho ~N~ chia hết cho ~K~. Ví dụ, tổng các ước số của 18 là:

~S(18)=1+2+3+6+9=21~

Một số hoàn hảo ~N>0~ là số mà tổng các ước số chặt ~S(N)~ của chính nó bằng ~N~. Ví dụ số 6 và 28 là số hoàn hảo:

~S(6)=1+2+3=6~

~S(28)=1+2+4+7+14=28~

Thực chất các số hoàn hảo rất hiếm. Vì vậy ở đây chúng ta quan tâm đến các số gần hoàn hảo, nghĩa là tổng các ước số chặt của ~N~ không quá xa ~N~.

Cho trước hai số ~L~ và ~D~ (~2 \le L \le 10^6~, ~0 \le D \le 10^6~), hãy tìm số các số nguyên dương nhỏ hơn ~L~ sao cho độ chênh lệch giữa nó và tổng các ước số chặt của nó không vượt quá ~D~.

Ví dụ, với ~L=10~, ~D=1~, ta tìm được 5 số thỏa mãn yêu cầu: 1, 2, 4, 6 và 8.

Input

Gồm 2 dòng:

• Dòng đầu tiên chứa số nguyên ~L~.
• Dòng thứ hai chứa số nguyên ~D~.

Output

In ra một số nguyên duy nhất là số lượng số tìm được.

Examples

Input

10
1

Output

5

Có ~n~ công việc phải hoàn thành, nhiệm vụ thứ ~i~ cần thời gian hoàn thành là ~d_i~ giây.

Nếu làm liên tiếp các nhiệm vụ và nhiệm vụ thứ ~i~ được làm sau ~x~ nhiệm vụ trước đó thì thời gian hoàn thành nhiệm vụ ~i~ sẽ là ~d_i \times 2^x~.

Tuy nhiên, nếu ta nghỉ giải lao sau ~1~ giờ (~3600~ giây) thì coi như bắt đầu lại với không nhiệm vụ nào làm trước đó.

Hãy tính tổng số giây nhỏ nhất để hoàn thành đủ ~n~ nhiệm vụ.

Input

• Dòng đầu chứa số ~n~ (~1 \le n \le 10^5~).
• Dòng tiếp theo chứa ~n~ số ~d_i~ (~1 \le d_i \le 28800~).

Output

In ra thời gian nhỏ nhất để hoàn thành đủ ~n~ nhiệm vụ.

Scoring

• Subtask 1 (30%): ~n \le 1000~.
• Subtask 2 (30%): ~d_1=d_2=\cdots=d_n~.
• Subtask 3 (40%): Không có ràng buộc gì thêm.

Examples

Input 1

3
999 1111 999

Output 1

7105

Input 2

4
999 1111 999 888

Output 2

9484

Các nhà khoa học đang muốn xây dựng một phòng thí nghiệm. Khu đất sẽ xây dựng phòng thí nghiệm phải có kích thước ~a \times b~, còn phòng thí nghiệm sẽ có kích thước ~c \times d~.

Các giá trị ~a~, ~b~, ~c~ và ~d~ vẫn chưa được xác định nhưng phải thỏa mãn các điều kiện sau:

• Độ dài các cạnh ~a~, ~b~, ~c~ và ~d~ phải là số tự nhiên.
• Để đảm bảo an toàn, chiều dài và chiều rộng của khu đất phải khác giá trị ~x~, nghĩa là ~a \ne x~ và ~b \ne x~.
• Phòng thí nghiệm phải nằm gọn trong khu đất, nghĩa là ~a > c~ và ~b > d~.
• Diện tích còn lại của khu đất sau khi xây dựng phòng thí nghiệm phải bằng ~n~, nghĩa là ~a \times b - c \times d = n~.

Các nhà khoa học muốn biết có bao nhiêu cách chọn các giá trị ~a~, ~b~, ~c~ và ~d~ thỏa mãn các điều kiện trên.

Input

Một dòng duy nhất chứa hai số nguyên ~n~ và ~x~ (~1 \le n \le 3000~, ~0 \le x \le 3000~).

Nếu ~x=0~ thì không có hạn chế về độ dài các cạnh của khu đất.

Output

In ra một số nguyên duy nhất là số cách chọn tìm được.

Examples

Input 1

3 0

Output 1

1

Input 2

5 0

Output 2

5

Input 3

5 3

Output 3

2

Xâu nhị phân là xâu chỉ chứa các ký tự 0 hoặc 1.

Một xâu nhị phân được gọi là đẹp nếu với mỗi ký tự 1 trong xâu, số lượng ký tự 0 liên tiếp từ nó tới ký tự 1 gần nhất bên trái (hoặc tới đầu xâu nếu không có) bằng số lượng ký tự 0 liên tiếp từ nó tới ký tự 1 gần nhất bên phải (hoặc tới cuối xâu nếu không có).

Nói cách khác, với mỗi ký tự 1, số lượng ký tự 0 liên tiếp ngay bên trái nó bằng số lượng ký tự 0 liên tiếp ngay bên phải nó.

Ví dụ:

• 0001000 là một xâu đẹp.
• 001010 không phải là xâu đẹp vì bên trái ký tự 1 đầu tiên có hai ký tự 0, còn bên phải chỉ có một ký tự 0.

Cho trước một xâu nhị phân, bạn được phép xóa một số ký tự để biến nó thành một xâu đẹp.

Hãy xác định độ dài lớn nhất của một xâu đẹp có thể thu được.

Input

• Dòng đầu tiên chứa số nguyên ~n~ là độ dài của xâu (~1 \le n \le 500000~).
• Dòng thứ hai chứa một xâu nhị phân độ dài ~n~, chỉ gồm các ký tự 0 và 1.

Đảm bảo xâu chứa ít nhất một ký tự 1.

Output

In ra một số nguyên duy nhất là độ dài của xâu đẹp dài nhất có thể thu được.

Examples

Input 1

10
0100100000

Output 1

7

Input 2

3
111

Output 2

3

Input 3

7
0100101

Output 3

5