PRMFN - 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
    

    hide comments
    nadstratosfer: 2018-11-25 07:21:25

    Appreciate lenient TL as this was a bit nasty to write. Would probably keep postponing getting it done if I wasn't sure a correct solution passes.

    -> Thank you. TL should be lenient ideally, unless that allows some sub-optimal solution to pass.

    Last edit: 2018-11-30 12:06:15

    Added by:sgtlaugh
    Date:2018-10-13
    Time limit:5s
    Source limit:50000B
    Memory limit:1536MB
    Cluster: Cube (Intel G860)
    Languages:All