h276. 淘汰赛进程

题目描述

有 $n$ 名选手参加单败淘汰赛。每一轮中，选手按当前顺序两两比赛，每场淘汰一人；如果本轮人数为奇数，最后一人轮空并直接进入下一轮。

请逐轮输出比赛场数和轮空人数，直到只剩冠军。

输入格式

输入一个整数 $n$。

输出格式

每轮输出一行两个整数，依次表示本轮比赛场数和轮空人数。若开始时只有一人，则不输出任何内容。

数据范围

• $1\le n\le 1000000000$。

样例

输入

5

输出

2 1
1 1
1 0

标签：模拟、整数运算