Cho \(N\) là một số nguyên dương lớn hơn 2. Xét tích \(T = 1 \times 2 \times 3 \times ... \times N\).

Yêu cầu: Trong các ước có dạng \(2^k\) (\(k \in N\)) của số \(T\), hãy tìm số mũ \(k\) lớn nhất.

Dữ liệu

• Một dòng chứ một số nguyên dương \(N\) (\(N < 10^8\)).

Kết quả

• Ghi ra số \(k\) theo yêu cầu trên.

Sample input

6

Sample output

4

Nguồn: TS10LQD 2020

Cho một sô nguyên dương \(k\) và một xâu ký tự \(S\). Xâu \(S\) chỉ gồm các ký tự là các chữ cái la tinh thường a..z và các chữ số 0..9, trong đó có ít nhất \(k\) ký tự là chữ số.

Yêu cầu Loại bỏ một số ký tự ra khỏi xâu \(S\) sao cho \(k\) ký tự còn lại theo đúng thứ tự đó tạo nên số nhỏ nhất. Trong \(k\) ký tự còn lại có thể cho phép các chữ số 0 đứng đầu.

Input

• Dòng thứ nhất chứa số nguyên dương \(k\).
• Dòng thứ hai chứa xâu \(S\).

Output

• Ghi ra gồm \(k\) ký lự còn lại của xâu \(S\) tạo nên số nhỏ nhất theo yêu câu trên.

Constraints

• \(k < 10\)
• Xâu \(S\) có độ dài nhỏ hơn 250

Example

4
307uv5x1y08mnp 

0108

Trên mặt phàng tọa độ \(Oxy\), cho 2 điểm \(A(m;n)\) và \(B(p;q)\). Vẽ đoạn thẳng \(AB\).

Yêu cầu: Hãy xác định có bao nhiêu điểm có hoành độ và tung độ là các số nguyên dương thuộc đoạn thẳng \(AB\) (không kể 2 mút của đoạn thẳng \(AB\)).

Input

• Một dòng chứa 4 số nguyên dương \(m, n, p, q\) nằm trên một dòng (\(m < p; n > q\)) mỗi số cách nhau 1 dấu cách. Trong đó \(m\) và \(n\) lần lượt là hoành độ và tung độ của điểm \(A\); \(p\) và \(q\) lần lượt là hoành độ và tung độ của điểm \(B\).

Output

• Ghi ra một số \(k\) là số các điểm có tọa độ là các số nguyên dương theo yêu cầu trên.

Constraints

• \(m, n, p, q < 10^9\)

Example

1 6 7 3

2

2 8 4 1

0

Nguồn: TS10LQD 2020