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.

样例输入复制

2

6

100

样例输出复制

Case #1: 5

Case #2: 73

#include <iostream>

#include <sstream>

#define ll long long

using namespace std;

int a[20]={317,	311,173,137,131,113,73,71,53,37,31,23,17,13,11,7,5,3,2,1};

int main()

{

	ios_base::sync_with_stdio(false);

    cin.tie(0);

    int T;

    cin>>T;

    for(int t=1;t<=T;t++)

    {

        int aa;

        stringstream aaa;

        string s;

        cin>>s;

        aaa<<s;

        aaa>>aa;

        int len=s.length();

        if(len>=4||aa>317) {

			cout<<"Case #"<<t<<": "<<a[0]<<endl;

			continue;

		}

 		if(aa==317) {

		 cout<<"Case #"<<t<<": "<<"317"<<endl;continue;

		 }

		for(int i=1;i<20;i++)

		{

			if(aa<a[i-1]&&aa>=a[i])

			{

				cout<<"Case #"<<t<<": "<<a[i]<<endl;

				break;

			}

		}

    }

    return 0;

}

这个题的题意，说的是给你一个大于等于2，且小于等于10的100次方，要你求的是，小于这个数，但是这个数要是素数，而且这个数里面任意x个数的组合也要是素数的数，x个数可以不连续。

首先输入很大， 所以使用了string类，读入一个字符串，然后用了stringstream，避免缓存溢出。因为将字符串转换为整数的方式可以用stdio里面的sprintf转换，但是由于数字太大，所以就换用stringstream这个字符串流。

然后就是枚举所有的是素数，而且每一位都是素数，且任何几位的组合都是素数的数，总共也就二十个，应该是吧，请读者自行验证之。

然后就是最上面的ios_base::sync_with_stdio(flase)解除绑定的，和cin.tie(0)都是加快cin的速度的。