# Prime String..

## Problem:-

Ankit has recently learned about ASCII values.He is very fond of experimenting. With his knowledge of ASCII values and character he has developed a special word and named it "Prime String" word.
A word which consist of alphabets whose ASCI values is a prime number is an Prime String word. An alphabet is Prime String alphabet if its ASCI value is prime.
Ankit's nature is to boast about the things he know or have learnt about. So just to defame his friends he gives few string to his friends and ask them to convert it to "Prime String" word. None of his friends would like to get insulted. Help them to convert the given strings to Prime String  Word.
Rules for converting:
1.Each character should be replaced by the nearest "Prime String" alphabet.
2.If the character is equidistant with 2 Prime alphabets. The one with lower ASCII value will be considered as its replacement.
Input format:
First line of input contains an integer `T` number of test cases. Each test case contains a string `S`.
Output Format:
For each test case, print Prime String Word in a new line.
Constraints:
1 <= T <= 50
1 <= |S| <= 500
SAMPLE INPUT

```2
abcd
abcm```
SAMPLE OUTPUT

```aaae
aaam
```
Time Limit:1.0 sec(s) for each input file.
Memory Limit:256 MB
Source Limit:1024 KB

## solution:-

#include<stdio.h>
void main()
{
int t,k,n,a,x;
char s[500];
scanf("%d",&t);
for(int i=0;i<t;i++)
{
scanf("%s",s);
for(int j=0;s[j]!='\0';j++)
{
x=s[j];
if(x<97)
{
s[j]='a';
continue;
}
n=x;
a=x;
for(k=2;k<n;k++)
{
if(n%k==0)
break;
}
if(k==n)
continue;
else
{
n--;
x++;
}
while(1){
for(k=2;k<n;k++)
{
if(n%k==0)
break;
}
if(k==n)
break;
else
n--;
}
while(1)
{
for(k=2;k<x;k++)
{
if(x%k==0)
break;
}
if(k==x)
break;
else
{
if(x>122)
{
x=n;
break;
}
x++;
}
}
if((x-a)>=(a-n))
s[j]=n;
else
s[j]=x;

}
printf("%s\n",s);
}
}