Cho xâu ~S~ chỉ gồm hai kí tự ~'a'~ và ~'b'~. Xâu ~XS~ là xâu được tạo bởi ghép ~X~ lần xâu ~S~ liền với nhau. Hãy đến xem có bao nhiêu xâu con ~"ab"~ xuất hiện trong xâu ~XS~.

Input

• Gồm hai dòng, dòng thứ nhất chứa xâu ~S~ có độ dài là ~N~ ~(0<N≤10^3)~.</li>
• Dòng thứ hai chứa số nguyên dương ~X~ ~(0<X≤10^9)~.</li>

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Subtask

• Có ~50\%~ số test tương ứng với số điểm có với ~N,X \le 50~
• Có ~30\%~ số test khác tương ứng với số điểm có với ~N,X \le 10^3~
• Có ~20\%~ số test còn lại tương ứng với số điểm không có giới hạn gì thêm.

Ví dụ

Input 1

aabb
2

Output 1

2

Giải thích 1

• Xâu ~XS=aabbaabb~ có ~2~ xâu con ~"ab"~.

Input 2

baba
2

Output 2

3

Giải thích 2

• Xâu ~XS=babababa~ có ~3~ xâu con ~"ab"~.

Input 3

aaa
1

Output 3

0

Giải thích 3

• Xâu ~XS=aaa~ có ~0~ xâu con ~"ab"~.

Cho dãy số có quy luật như sau: ~1,2,2,3,3,3,4,4,4,4,5,5,…~ Cho một số tự nhiên ~N~, hãy tìm số thứ ~N~ của dãy số trên (các số được đánh thứ tự từ ~1~).

Input

• Gồm một số nguyên dương ~N~ ~(N ≤ 10^{15})~.

Output

• In ra kết quả của bài toán.

Subtasks

• Subtask 1 (~60\%~ số điểm): ~N ≤ 10^{6}~;
• Subtask 2 (~20\%~ số điểm): ~N ≤ 10^{10}~;
• Subtask 3 (~20\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test

Input

5

Output

3

Cho một xâu ~S~ gồm các kí tự số. Hãy đếm xem có bao nhiêu xâu con chia hết cho ~4~ (xâu con có thể bắt đầu bằng ~0~).

Input:

Xâu ~S~ có độ dài không quá ~10^6~.

Output:

In ra kết quả của bài toán.

Scoring

• Subtask 1 [60%]: Xâu ~S~ có độ dài không quá ~100~.
• Subtask 2 [40%]: Không có ràng buộc gì thêm.

Examples

Input1

08

Output1

3

Giải thích

~0, 8, 08~

Input2

13085

Output2

5