Аутор: Иван Драцун

Такмичење: државно 2021/22., VII и VIII разред, 4. задатак

Професор Душан данима ломи главу око веома тешког математичког проблема. Жели да докаже да је број \(n\) природан број. Доказ започиње тиме што на таблу напише један од најпознатијих природних бројева, број 1. Након тога, у сваком кораку доказа, он бира два броја (не нужно различита) написана на табли, рачуна њихов збир и резултат записује на таблу. Доказ је завршен када је број \(n\) написан на табли. Напиши програм који ће помоћи професору да докаже ово компликовано тврђење.

Опис улаза

Са стандардног улаза се уноси број \(n\) (\(2 \leq n \leq 10^{18}\)).

Додатна ограничења:

• \(n \leq 10^4\) у примерима вредним 20% поена
• \(n \leq 4 \cdot 10^7\) у примерима вредним 60% поена

Опис излаза

На стандардни излаз исписати доказ да је \(n\) природан број. Доказ се састоји из више корака, при чему је сваки корак облика a=b+c (без размака) где су \(b\) и \(c\) вредности које су већ написане на табли, а \(a\) вредност која се у том кораку записује на таблу. Сваки корак исписати у засебном реду стандардног излаза.

Пример

Улаз

5

Излаз

2=1+1
3=2+1
5=2+3