The universe is at war again because of the Alien oppressive ruler Hitla
Nagasaki. Hitla is so brutal that it throws all beings of a race into black hole
after conquest against one. Now the evil has its mind set to conquest
As Hitla’s race is far superior in technology, head to head survival chance of
mankind is negligible. So we need to know the exact positions of alien
armies. For that we need to intercept and interpret their messages. As
aliens are very cunning, they have their messages highly encrypted and use
a key buried as substring inside the message to decrypt it. Recent
intelligence report confirms that the key is the biggest prime number and if
a number does not contain any key then this message is just some junk to
confuse the enemies. Now mankind needs a great programmer to crack
Unfortunately Hitla has assassinated all programmers but you
due to the fear of cracking messages. Now the fate of mankind depends on
First line of input contains an integer T denoting the number of test cases
followed by T lines. Each line contains an integer N and a string S denoting
the length of the message and the message.
For each case output must be of the following format Case
X: Y where X is the number of test case starting from 1
and Y is the biggest prime number if there is any.
Otherwise Y will be a string stating This is a junk!.
T ≤ 100
0 < N ≤ 10000
Biggest prime number < 10000
4 9 123456789 6 890097 10 4444466666 10 2356122351
Case 1: 4567 Case 2: 97 Case 3: This is a junk! Case 4: 2351
Substring of "123" are "", "1","2", "3", "12", "23", "123"
In first case, substrings which are prime and less than
10000 are 2, 23, 3, 4567, 5, 67, 7, 89. Among which 4567
is the biggest.
In second case, substrings which are prime and less
than 10000 are 89 and 97. Among which 97 is the
In third case, there is no substring which is prime.