Consider 24-hour times in the format HH:MM ranging from 00:00 (midnight) to 23:59 (1 minute before midnight) mapping to the “time numbers” between 0 (0000) and 2359. Note that there are 60*24 = 1440 such numbers only since times such as 0060 (actually 0100) or 1071 (actually 1111) are invalid.
Given an integer M, the objective is to identify a time interval M minutes apart in which both the starting time and ending time are “prime time numbers”. Note that a time HH:MM is a prime time number if the four digit number HHMM is a prime. For example 00:02, 00:03, 00:07, 23:51 are prime time numbers, while 00:10 is not.
Input
One line giving a positive integer M.
Output
The earliest interval bounded by prime time numbers (starting and ending times in HH:MM format separated by a hyphen) that is separated by M minutes. If no such interval exists, the output should be “NONE”…
Constraints
0<M<2880
Example 1
Input:
30
Output:
00:07-00:37
Explanation:
From the input, M = 30
Scanning 30 minute time intervals, we observe:
0002 - 0032 (end time not prime)
0003 - 0033 (end time not prime)
0005 - 0035 (end time not prime)
0007 - 0037 (end time is prime!)
Hence the output is 00:07-00:37
Example 2
Input:
13
Output:
NONE
Explanation:
M is 13 as specified in the input. Considering possible values of start time,
0002 - 0015 (end time not prime)
…
2347 - 0000 (end time not prime)
2351 - 0004 (end time not prime)
2357 - 0010 (end time not prime)
Hence there are no 13 minute intervals bound by primes. The output is NONE.