题目描述

若将一个正整数转换为二进制数，在此二进制数中，我们将数字1的个数多于数字0的个数的这类二进制数称为$A$类数，否则就称其为$B$类数。

例如

（1）10=（1）2

其中1的个数为1，0的个数为0，则称此数为A类数；

（13）10=（1101）2

其中1的个数为3，0的个数为1，则称此数为A类数；

（10）10=（1010）2

其中1的个数为2，0的个数也为2，称此数为B类数；

（24）10=（11000）2

其中1的个数为2，0的个数为3，则称此数为B类数；

编程输出1～$n$之中（包括1和$n$），$A、B$两类数的个数。

输入格式

输入文件一行，为一个正整数$n$（$1\leqslant n\leqslant 20,000,000$)

输出格式

输出文件一行，为空格隔开的两个整数$a$和$b$，其中$a$表示$A$类数的个数，$b$表示$B$类数的个数；

样例

3

2 1

11

6 5

数据范围与提示:

• 对于50%的数据，满足$n\leqslant 1000$
• 对于100%的数据，满足$n\leqslant 20,000,000$

来源

NOIP 1995 T2