#PRMFN. Prime Friendly Numbers

    ID: 3801 远端评测题 5000ms 1536MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>dynamic-programminggreedyprimality-test

Prime Friendly Numbers

Given N, find the largest number X not greater than N such that X is prime friendly. A number is called prime friendly when it satisfies both of the following conditions:

  1. The number itself is a prime.
  2. All its digits in base 10 are also primes. In other words, the number consists of only the digits 2, 3, 5, 7.

Input

The first line contains an integer T, denoting the number of test cases. Each test case contains a single positive integer N.

Constraints

  • 1 < T ≤ 1000
  • 1 < N ≤ 1018

Output

For each test case, output the case number followed by the largest number X not greater than N. Please refer to the sample input/output section for more clarity of the format.

Example

Input:
5
10
100
1000
10000
100000

Output: Case 1: 7 Case 2: 73 Case 3: 773 Case 4: 7757 Case 5: 77773

</p>