Load balancing (负载均衡) refers to efficiently distributing incoming network traffic across a group of backend servers. A load balancing algorithm distributes loads in a specific way.

If we can estimate the maximum incoming traffic load, here is an algorithm that works according to the following rule:

• The incoming traffic load of size S will first be partitioned into two parts, and each part may be again partitioned into two parts, and so on.

• Only one partition is made at a time.

• At any time, the size of the smallest load must be strictly greater than half of the size of the largest load.

• All the sizes are positive integers.

• This partition process goes on until it is impossible to make any further partition.

For example, if S=7, then we can break it into 3+4 first, then continue as 4=2+2. The process stops at requiring three servers, holding loads 3, 2, and 2.

Your job is to decide the maximum number of backend servers required by this algorithm. Since such kind of partitions may not be unique, find the best solution -- that is, the difference between the largest and the smallest sizes is minimized.

#### Input Specification:

Each input file contains one test case, which gives a positive integer S (2≤N≤200), the size of the incoming traffic load.

#### Output Specification:

For each case, print two numbers in a line, namely, M, the maximum number of backend servers required, and D, the minimum of the difference between the largest and the smallest sizes in a partition with M servers. The numbers in a line must be separated by one space, and there must be no extra space at the beginning or the end of the line.

#### Sample Input:

``22``

#### Sample Output:

``4 1``

#### Hint:

There are more than one way to partition the load. For example:

``````22
= 8 + 14
= 8 + 7 + 7
= 4 + 4 + 7 + 7``````

or

``````22
= 10 + 12
= 10 + 6 + 6
= 4 + 6 + 6 + 6``````

or

``````22
= 10 + 12
= 10 + 6 + 6
= 5 + 5 + 6 + 6``````

All requires 4 servers. The last partition has the smallest difference 6−5=1, hence 1 is printed out.

``````#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <map>
#include <queue>
using namespace std;
const int maxn = 210;
int n,maxnum=-1,mindis=maxn,length[maxn]={0};
//最长木棍，最短，数量
//遍历的目的是让它一直掰下去，然后筛选出满足条件的解
void dfs(int min_l,int max_l,int count){
if(count>maxnum){
maxnum=count;
mindis = max_l-min_l;
}
else if(count==maxnum && mindis>(max_l-min_l)){
mindis = max_l-min_l;
}
//选出第二长的木棍，方便到时候判断截断的两根是否合规
int max2=max_l;
length[max_l]--;//取出最长木棍
if(length[max_l]==0){
for(max2=max_l-1;max2>=2;max2--){
if(length[max2]!=0) break;
}
}
//选择的是较长木棍截断后较短的那根
for(int i=max_l/2;i>=max_l/3+1;i--){
if(i*2<=max2) break;
int j=max_l-i;
length[i]++;
length[j]++;
dfs(i,max(j,max2),count+1);
length[i]--;
length[j]--;
}
length[max_l]++;
}
int main()
{
scanf("%d",&n);
length[n]=1;
dfs(n,n,1);
printf("%d %d\n",maxnum,mindis);
return 0;
}`````` 