Description

若将一个正整数转换为二进制数，在此二进制数中，我们将数字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两类数的个数。

Format

Input

输入文件一行，为一个正整数n（1≤n≤60,000,000)

Output

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

Samples

3

2 1

Limitation

1s, 256MiB for each test case.