Problem Description

A customer urgently needs chocolate of size $K$ units, but you can only buy one bar whose size is a non-negative integer power of $2$ (that is, $1, 2, 4, 8, 16, \cdots$).

To meet the customer’s needs, you may cut the chocolate. A bar of size $D$ units can be cut into two bars of size $\dfrac{D}{2}$ units each.

To reduce cost, you need to find the minimum possible chocolate size to buy and the minimum number of cuts needed.

Input Format

The first line contains one positive integer $K$, which is the size of chocolate the customer needs.

Output Format

Output two integers: the minimum chocolate size to buy, and the minimum number of cuts required.

6

8 2

7

8 3

5

8 3

Hint

【Constraints】

• For $100\%$ of the testdata, $1 \le K \le 10^6$.

【Hints and Notes】

This problem is translated from COCI 2009-2010 CONTEST #7 Task 2 COKOLADA.

The score settings follow the original COCI problem. The full score is $50$.

Translated by ChatGPT 5