Indigo Real-estate Company is now planning to develop a new housing complex. The entire complex is a square, all of whose edges are equally a meters. The complex contains n subdivided blocks, each of which is a b-meter square. Here both a and b are positive integers.

However the project is facing a big problem. In this country, a percentage limit applies to the subdivision of a land, under the pretext of environmental protection. When developing a complex, the total area of the subdivided blocks must not exceed 50% of the area of the complex; in other words, more than or equal to 50% of the newly developed housing complex must be kept for green space. As a business, a green space exceeding 50% of the total area is a dead space. The primary concern of the project is to minimize it.

Of course purchasing and developing a land costs in proportion to its area, so the company also wants to minimize the land area to develop as the secondary concern. You, a member of the project, were assigned this task, but can no longer stand struggling against the problem with your pencil and paper. So you decided to write a program to find the pair of minimum a and b among those which produce the minimum dead space for given n.



Input

The input consists of multiple test cases. Each test case comes in a line, which contains an integer n. You may assume 1 ≤ n ≤ 10000.

The end of input is indicated by a line containing a single zero. This line is not a part of the input and should not be processed.

Output

For each test case, output the case number starting from 1 and the pair of minimum a and b as in the sample output.

You may assume both a and b fit into 64-bit signed integers.

Example

Input

1
2
0


Output

Case 1: 3 2
Case 2: 2 1
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cassert>
#include<cmath>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
typedef pair<lint,lint>pll;
typedef pair<pll,lint>pplll;
#define rep(i,n)for(int i=0;i<(int)(n);++i)

pll fundamental_unit(lint d){
  vi ans;
  lint x=0,y=1,z=1;//(x+y*sqrt(d))/z
  double sqrtd=sqrt(d);
  set<pplll>seen;
  while(1){
    if(seen.count(pplll(pll(x,y),z)))break;
    seen.insert(pplll(pll(x,y),z));
    lint q=floor((x+sqrtd*y)/z);
    if(0){
      cerr<<"x,y,z=("<<x<<"+"<<y<<"*sqrt(d))/"<<z<<endl;
      cerr<<"q="<<q<<endl;
    }
    ans.push_back(q);
    x-=q*z;
    lint norm=x*x-d*y*y;
    y=-y;
    z=norm/z;
    if(z<0){
      x=-x;y=-y;z=-z;
    }
  }
  // recover
  lint num=0,den=1;
  for(int i=(int)ans.size()-2;i>=0;--i){
    lint z=num+ans[i]*den;
    num=den;den=z;
  }
  if(den*den-d*num*num==-1){
    lint x=den*den+d*num*num;
    lint y=2*den*num;
    den=x;num=y;
  }
  assert(den*den-d*num*num==1);
  return pll(den,num);
}

pll solve(lint n){
  rep(i,200)
    if(i*i==2*n)
      return pll(i,1);
  return fundamental_unit(2*n);
}

int main(){
  for(int t=1;;++t){
    lint n;
    cin>>n;
    if(n==0)break;
    pll ans=solve(n);
    cout<<"Case "<<t<<": "<<ans.first<<" "<<ans.second<<endl;
  }
}

