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 <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
int sum[] = {
1,
2,
3,
5,
7,
11,
13,
17,
23,
31,
37,
53,
71,
73,
113,
131,
137,
173,
311,
317,
48481548
};
const int binggg=317;
string s;
int toint(const string &s) {
stringstream ss;
ss<<s;
int res;
ss>>res;
return res;
}
int solve(int n) {
if(n>=binggg) return binggg;
for(int i=0; ;i++) {
if(sum[i+1]>n) return sum[i];
}
}
int main() {
int T;
int kase=1;
cin>>T;
while(T--) {
cin>>s;
cout<<"Case #"<<kase++<<": ";
if(s.size()>5) cout<<binggg<<endl;
else {
int n=toint(s);
cout<<solve(n)<<endl;
}
}
}