壹数和零数(onezero)

题目描述

百无聊赖的 cc 在纸上随便写了一个正整数 13，让小 d 把它转化为二进制。很快小 d 就把答案算出来了：1101。cc 发现答案中 1 的个数比 0 的个数多，于是他给 13 这种正整数起了个名字——壹数，而把不是壹数的正整数统称为零数。他突发奇想，提出来这样一个问题：任意给出一个正整数 n，在不超过 n 的正整数 中有多少个壹数和零数呢？这下可把小 d 难住了。你能帮帮他吗？

输入格式

一行，一个正整数 n

输出格式

一行，两个整数，依次表示壹数和零数的个数，中间以一个空格隔开。

样例输入

3

样例输出

2 1

样例解释

1、2、3 的二进制分别为 1,10,11，其中有 2 个数是壹数：1 和 3，有 1 个数是零数：2。

数据范围

对于 40% 的数据，满足 n ≤ 1,000

对于 100% 的数据，满足 n ≤ 20,000,000