Ra = [ (a−1)n + (a+1)n ] %a2 ,(n>0)
例如当a=4, n=2时，Ra=32 +52 =34，而34%16 =2,故Ra=2。由于n可以是任意大于0的正整数，所以存在很多Ra的解，找到任意一个Ra就算做出来这道题。例如，当a=4的时候，Ra的取值可以是2或者是8。
“你怎么这么有空还管闲事，不赶紧去补题吗...”，JAJA_Xin被魏队一顿说了之后闷闷不乐，不小心就把原题意记成了要找到最大的Ra才能算做出来这道题，并把修改的题意后和师妹说了，这可难到他们了。例如，当a=4的时候，Ra_max=8。
多测试用例，用例不超过10000个。每个用例有一行数据，一个整数a (3≤a≤1000000)。
对于每个用例输出一行，Ra_max。