Guess Number

Bính và Thân đang chơi trò chơi đoán số. Bính nghĩ ra một số nguyên x nằm trong khoảng từ 1 đến n, và Thân sẽ là người phải đoán số nguyên đó. Thân có thể hỏi Bính các câu hỏi có dạng: “Số nguyên Bính đang nghĩ có chia hết cho số nguyên y không? “

Luật chơi của trò chơi như sau: đầu tiên Thân sẽ hỏi tất cả các hỏi mà Thân muốn (số lượng câu hỏi là tùy thích, Thân có thể không hỏi câu nào), sau đó Bính sẽ trả lời tất cả các câu hỏi rằng “Có” hoặc “Không”. Sau khi nhận được tất cả các câu trả lời, Thân sẽ phải đoán xem số Bính đang nghĩ là bao nhiêu.

Thật không may, Thân không giỏi số học cho lắm, bạn hãy giúp Thân tìm số câu hỏi nhỏ nhất mà Thân cần phải hỏi để sao cho dù Bính có chọn số nào thì Thân cũng có thể đoán ra.

Input:

-         Gồm một dòng duy nhất chứa số nguyên n (1 ≤ n ≤ 10⁵)

Output:

-         Ghi ra một dòng duy nhất là kết quả của bài toán

Example:

Input	Output
4	3
6	4

Với n = 4, Thân sẽ hỏi với các số y = 2, y = 4, y = 3. Nếu 3 lần trả lời của Bính lần lượt là: Không, Không, Không thì đó là số 1; Có, Không, Không thì đó là số 2; Không, Không, Có thì đó là số 3; Có, Có, Không thì đó là số 4. Như vậy với tối thiểu là 3 lần hỏi Thân sẽ đoán ra được số Bính nghĩ dù đó là bất cứ số nào.

Subtask 1: (50%) n ≤ 10³

Subtask 2: (50%) n ≤ 10⁵