Euler's Totient function,φ (n) [sometimes called the phi function],is used to determine the number of numbers less than n which are relatively prime to n . For example,as 1,2,4,5,7,and 8,are all less than nine and relatively prime to nine,φ(9)=6.
HG is the master of X Y. One day HG wants to teachers XY something about Euler's Totient function by a mathematic game. That is HG gives a positive integer N and XY tells his master the value of 2<=n<=N for which φ(n) is a maximum. Soon HG finds that this seems a little easy for XY who is a primer of Lupus,because XY gives the right answer very fast by a small program. So HG makes some changes. For this time XY will tells him the value of 2<=n<=N for which n/φ(n) is a maximum. This time XY meets some difficult because he has no enough knowledge to solve this problem. Now he needs your help.

There are T test cases (1<=T<=50000). For each test case,standard input contains a line with 2 ≤ n ≤ 10^100.

For each test case there should be single line of output answering the question posed above.

  
  

   
   2
10
100
  
  

  
  

   
   6
30


   
   
 
    
 
     Hint 
    
If the maximum is achieved more than once,we might pick the smallest such n. 
   
   
   

     //题意： 
    给出一个n，求一个数x，x在1到n之间，并且x/φ(x)最大(其中φ(x)为x的欧拉函数)。 
   
   
   
 
    //想了很久，就是不知怎么打表，看网上的竟然直接打好，先贴上，有时间在慢慢琢磨。 
   
   
   
 
    
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#define N 110
using namespace std;
char a[][110] =
{
        "2","6","30","210","2310","30030","510510","9699690","223092870","6469693230","200560490130","7420738134810","304250263527210","13082761331670030","614889782588491410","32589158477190044730","1922760350154212639070","117288381359406970983270","7858321551080267055879090","557940830126698960967415390","40729680599249024150621323470","3217644767340672907899084554130","267064515689275851355624017992790","23768741896345550770650537601358310","2305567963945518424753102147331756070","232862364358497360900063316880507363070","23984823528925228172706521638692258396210","2566376117594999414479597815340071648394470","279734996817854936178276161872067809674997230","31610054640417607788145206291543662493274686990","4014476939333036189094441199026045136645885247730","525896479052627740771371797072411912900610967452630","72047817630210000485677936198920432067383702541010310","10014646650599190067509233131649940057366334653200433090","1492182350939279320058875736615841068547583863326864530410","225319534991831177328890236228992001350685163362356544091910","35375166993717494840635767087951744212057570647889977422429870","5766152219975951659023630035336134306565384015606066319856068810","962947420735983927056946215901134429196419130606213075415963491270","166589903787325219380851695350896256250980509594874862046961683989710","29819592777931214269172453467810429868925511217482600306406141434158090","5397346292805549782720214077673687806275517530364350655459511599582614290","1030893141925860008499560888835674370998623848299590975192766715520279329390","198962376391690981640415251545285153602734402721821058212203976095413910572270","39195588149163123383161804554421175259738677336198748467804183290796540382737190","7799922041683461553249199106329813876687996789903550945093032474868511536164700810","1645783550795210387735581011435590727981167322669649249414629852197255934130751870910","367009731827331916465034565550136732339800312955331782619462457039988073311157667212930","83311209124804345037562846379881038241134671040860314654617977748077292641632790457335110","19078266889580195013601891820992757757219839668357012055907516904309700014933909014729740190","4445236185272185438169240794291312557432222642727183809026451438704160103479600800432029464270","1062411448280052319722448549835623701226301211611796930357321893850294264731624591303255041960530","256041159035492609053110100510385311995538591998443060216114576417920917800321526504084465112487730","64266330917908644872330635228106713310880186591609208114244758680898150367880703152525200743234420230"
};
char s[N];
int main()
{
	int t,i;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s);
		int x=strlen(s);
		for(i=0;i<60;i++)
		{
			int y=strlen(a[i]);
			if(x<y)
				break;
			if(x>y)
				continue;
			if(strcmp(s,a[i])<0)
				break;
		}
		printf("%sn",a[i-1]);
	}
	return 0;
}