A prime number (or a prime) is a natural number greater than 11 that cannot be formed by multiplying two smaller natural numbers.

Now lets define a number NN as the supreme number if and only if each number made up of an non-empty subsequence of all the numeric digits of NN must be either a prime number or 11.

For example, 1717 is a supreme number because 11, 77, 1717 are all prime numbers or 11, and 1919 is not, because 99 is not a prime number.

Now you are given an integer N\ (2 \leq N \leq 10^{100})N (2≤N≤10100), could you find the maximal supreme number that does not exceed NN?

Input

In the first line, there is an integer T\ (T \leq 100000)T (T≤100000) indicating the numbers of test cases.

In the following TT lines, there is an integer N\ (2 \leq N \leq 10^{100})N (2≤N≤10100).

Output

For each test case print "Case #x: y", in which xx is the order number of the test case and yy is the answer.

样例输入复制

26100

样例输出复制

Case #1: 5Case #2: 73

题目来源

 题目意思：

给定长度达100的整数，要使 

@这个数是质数或者1

@数字的每一位都必须是1或2或3或5或7

@数字的子序列所组成的数字也必须是质数。

比如317,3和1和7和31和37和17和317都是质数，那么317这个数字就符合标准。

题目思路：

考虑到答案中任意一位都必须是1或质数，可知答案只可能由1、2、3、5、7构成。由于任意两个不为1的数字构成 的两位数一定可以被11整除，所以答案中除1外的数字只能出现一次；1最多出现2次，因为111可以被3整除；而 2、5、7三者一定不会有两者同时出现。因此满足条件的整数不会超过四位，全部预处理出来即可。

方法：先打表

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;bool isprime(int x){	for (int i=2;i*i<=x;i++)	{		if (x%i==0)		return false;	}	return true;}bool check(int x){	int a=x%10;	int b=x/10%10;	int c=x/100;		int x1=a*10+b;	int x2=a*10+c;	int x3=b*10+c;	 	if (x>=1&&x<=9)	{		if (x==1||x==2||x==3||x==5||x==7)		return true;		else		return false;	}	else if (x>=10&&x<=99)	{		if (a!=1&&a!=2&&a!=3&&a!=5&&a!=7)		return false;		else if (b!=1&&b!=2&&b!=3&&b!=5&&b!=7)		return false;		else if (isprime(x)==false)		return false;		else		return true;	}	else if (x>=100&&x<=999)	{		if (a!=1&&a!=2&&a!=3&&a!=5&&a!=7)		return false;		else if (b!=1&&b!=2&&b!=3&&b!=5&&b!=7)		return false;		else if (c!=1&&c!=2&&c!=3&&c!=5&&c!=7)		return false;		else if (isprime(x1)==false ||isprime(x2)==false||isprime(x3)==false )		return false;		else if (isprime(x)==false)		return false;		else		return true;	}}int main(){	for (int i=2;i<=999;i++)	if (check(i))	cout<
        <
       
      
     
    

得到数值为 ：

2,3,5,7,11,13,17,23,31,37,53,71,73,113,131,137,173,311,317

所以答案代码为：

 

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int main(){	int n,m,j,k,i,T,cas=0,num;	char a[1000];	int  ans[]={2,3,5,7,11,13,17,23,31,37,53,71,73,113,131,137,173,311,317}; 		cin>>T;	getchar();	while (T--)	{		cas++;		num=0;		scanf("%s",a);		int len=strlen(a);		if (len>3)		{			printf("Case #%d: 317\n",cas);			continue;		}		j=0;		for (i=len-1;i>=0;i--)		num +=   (a[i]-'0')*pow(10,j++);		//cout<<"num="<
        
         <
         
          =0;i--) { if (num>=ans[i]) { printf("Case #%d: %d\n",cas,ans[i]); break; } } } return 0;}