С наступлением нового учебного года студенты второго курса начали изучать новые дисциплины, такие как АКиОс, новые языки программирования и математики. После очередной контрольной по теории вероятностей, преподаватель решил, что требуется провести нормировку, поэтому обратился к вам пообещав дополнительный балл.

Нормировка проходит следующим образом: score = score / 3;

Но всё не так просто, это услышал преподаватель по АКиОс и запретил вам использовать деление и циклы.

Ваша задача написать программу, которая нормирует заданное 16-битное беззнаковое число. Операторы умножения, деления, сложения, вычитания и циклы использовать запрещено.

Подсказка

Программа принимает на вход единственное целое число.

Программа выводит полученное целое число.

Examples

Input

9
Output

3
 

Submit a solution

Language:	gcc - GNU C 11.3.0
Подсказка:
Division by a constant
The division by a constant D is equivalent to the multiplication by its reciprocal. Since the denominator is constant, so is its reciprocal (1/D). Thus it is possible to compute the value of (1/D) once at compile time, and at run time perform the multiplication N·(1/D) rather than the division N/D. In floating-point arithmetic the use of (1/D) presents little problem,[a] but in integer arithmetic the reciprocal will always evaluate to zero (assuming |D| > 1).

It is not necessary to use specifically (1/D); any value (X/Y) that reduces to (1/D) may be used. For example, for division by 3, the factors 1/3, 2/6, 3/9, or 194/582 could be used. Consequently, if Y were a power of two the division step would reduce to a fast right bit shift. The effect of calculating N/D as (N·X)/Y replaces a division with a multiply and a shift. Note that the parentheses are important, as N·(X/Y) will evaluate to zero.

However, unless D itself is a power of two, there is no X and Y that satisfies the conditions above. Fortunately, (N·X)/Y gives exactly the same result as N/D in integer arithmetic even when (X/Y) is not exactly equal to 1/D, but "close enough" that the error introduced by the approximation is in the bits that are discarded by the shift operation.[21][22][23] Barrett reduction uses powers of 2 for the value of Y to make division by Y a simple right shift.[b]

As a concrete fixed-point arithmetic example, for 32-bit unsigned integers, division by 3 can be replaced with a multiply by ⁠
2863311531
/
233
⁠, a multiplication by 2863311531 (hexadecimal 0xAAAAAAAB) followed by a 33 right bit shift. The value of 2863311531 is calculated as ⁠
233
/
3
⁠, then rounded up. Likewise, division by 10 can be expressed as a multiplication by 3435973837 (0xCCCCCCCD) followed by division by 235 (or 35 right bit shift).[25]: p230-234  OEIS provides sequences of the constants for multiplication as A346495 and for the right shift as A346496.

For general x-bit unsigned integer division where the divisor D is not a power of 2, the following identity converts the division into two x-bit addition/subtraction, one x-bit by x-bit multiplication (where only the upper half of the result is used) and several shifts, after precomputing 
k
=
x
+
⌈
log
2
⁡
D
⌉
{\displaystyle k=x+\lceil \log _{2}{D}\rceil } and 
a
=
⌈
2
k
D
⌉
−
2
x
{\displaystyle a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}}:

⌊
N
D
⌋
=
⌊
⌊
N
−
b
2
⌋
+
b
2
k
−
x
−
1
⌋
 where 
b
=
⌊
N
a
2
x
⌋
{\displaystyle \left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {N-b}{2}}\right\rfloor +b}{2^{k-x-1}}}\right\rfloor {\text{ where }}b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor }
In some cases, division by a constant can be accomplished in even less time by converting the "multiply by a constant" into a series of shifts and adds or subtracts.[26] Of particular interest is division by 10, for which the exact quotient is obtained, with remainder if required.[27]