题目描述

百无聊赖的小明在纸上随便写了一个正整数 13，让小红把它转化为二进制，不能有前导 0。小红很快就把答案算出来了：1101。

小明发现答案中 1 的个数比 0 的个数多，于是他给 13 这种正整数起了个名字——重数，而把不是重数的正整数统称为轻数。

他突发奇想，提出来这样一个问题：任意给出一个正整数 n，在不超过 n 的正整数中有多少个重数和多少个轻数呢？

这下可把小红难住了。

你能帮帮她吗？

输入格式

一行，一个正整数 n

输出格式

一行，两个整数，依次表示在不超过 n 的正整数中重数和轻数的个数，中间以一个空格隔开。

样例输入

3

样例输出

2 1

样例解释

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

数据范围

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

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