题目背景

小 R 在学习二进制时，老师介绍了十进制转二进制的除法过程。小 R 觉得手动算太麻烦，于是想找一个程序来展示每一步的商和余数。

题目描述

将一个正整数 $n$ 不断除以 $2$，每次记录商和余数，然后用商替换原来的数字，直到商变为 $0$ 为止。

请输出每一步得到的商和余数。

输入格式

一行，一个正整数 $n$，表示待转换的数字。

输出格式

输出若干行，每一行两个数字 $x_i$ 和 $y_i$，表示第 $i$ 次除法得到的商和余数。你应该保证 $y_i$ 是 $0$ 或 $1$。

样例

9

4 1
2 0
1 0
0 1

22

11 0
5 1
2 1
1 0
0 1

1

0 1

提示

样例 1 解释

首先，$9 = 2 \times 4 + 1$，所以第一行输出 4 1，并令 $9$ 变为 $4$；
然后，$4 = 2 \times 2 + 0$，所以第二行输出 2 0，并令 $4$ 变为 $2$；
接着，$2 = 2 \times 1 + 0$，所以第三行输出 1 0，并令 $2$ 变为 $1$；
最后，$1 = 2 \times 0 + 1$，所以第四行输出 0 1，结束。

数据范围

对于 $30\%$ 的数据，$1 \le n \le 100$；
对于 $100\%$ 的数据，$1 \le n \le 10^{18}$。