using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;
namespace AIZUproject08
{
    //128B
    /*class Data
    {
        public int ID { get; set; }
        public string Name { get; set; }
        public int Evaluation { get; set; }
    }
    class Program
    {
        static void Main()
        {
            List<Data> datalist = new List<Data>();
            Data data;
            int N = int.Parse(Console.ReadLine());
            for (int i=0;i< N;i++)
            {
                var temp = Console.ReadLine().Split(' ');
                data = new Data();
                data.ID = i + 1;
                data.Name = temp[0];
                data.Evaluation = int.Parse(temp[1]);
                datalist.Add(data);
            }
            datalist = datalist.OrderBy(n => n.Name).ThenByDescending(n => n.Evaluation).ToList();
            foreach (var ans in datalist)
            {
                Console.WriteLine(ans.ID);
            }
        }
    }*/
    //127B
    /*class Program
    {
        static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int r = input[0];
            int D = input[1];
            int X = input[2];
            for (int i=0;i<10;i++)
            {
                var ans = r * X - D;
                Console.WriteLine(ans);
                X = ans;
            }
        }
    }*/
    //126B
    /*class Program
    {
        static void Main()
        {
            List<int> mae = new List<int>();
            List<int> ushiro = new List<int>();
            string input = Console.ReadLine();
            var rabel = "NA";
            for (int i = 0; i < 2; i++)
            {
                char moji = input[i];
                mae.Add(int.Parse(string.Join("",moji)));
            }
            for (int i = 2; i < 4; i++)
            {
                char moji = input[i];
                ushiro.Add(int.Parse(string.Join("", moji)));
            }
            int A = 10 * mae[0] + 1 * mae[1];
            int B = 10 * ushiro[0] + 1 * ushiro[1];

            if (0 <= A && A <= 99 && 0 < B && B < 13)
            {
                rabel = "YYMM";
                if (0 < A && A < 13 && 0 < B && B < 13)
                {
                    rabel = "AMBIGUOUS";
                }
            }
            else if (0 <= B && B <= 99 && 0 < A && A < 13)
            {
                 rabel = "MMYY";
                if (0 < A && A < 13 && 0 < B && B < 13)
                {
                    rabel = "AMBIGUOUS";
                }
            }
            Console.WriteLine(rabel);
        }
    }*/
    //125B
    /*class Program
    {
        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int[] V = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] C = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int Answer = 0;
            for (int i=0;i<N;i++)
            {
                var temp = V[i] - C[i];
                if (temp > 0)
                {
                    Answer += temp;
                }
            }
            
            Console.WriteLine(Answer);
        }
    }*/
    //124B
    //count変数の初期化忘れがち!!
    /*class Program
    {
        static void Main()
        {
            int Ans = 0;
            int count = 0;
            int N = int.Parse(Console.ReadLine());
            int[] Height = Console.ReadLine().Split().Select(int.Parse).ToArray();
            for (int i =0;i<Height.Length;i++)
            {
                for (int j=0;j<i;j++)
                {
                    if (Height[i] >= Height[j])
                    {
                        Ans++;
                    }
                }
                if (Ans == i)
                {
                    count++;
                }
                Ans = 0;
            }
            Console.WriteLine(count);
        }
    }*/
    //123B
    /*class Program
    {
        static void Main()
        {
            List<int> time = new List<int>();
            List<int> sample = new List<int>();
            int[] aa = new int[5];
            for (int i = 0;i<5;i++)
            {
                int dish = int.Parse(Console.ReadLine());
                time.Add(dish);
            }
            time.CopyTo(aa);
            int ans = 0;
            foreach (int a in time)
            {
                var temp = a % 10;
                sample.Add(temp);
            }
            var jj = sample.IndexOf(sample.Min());
            time.RemoveAt(jj);
            time.Add(aa[jj]);

            foreach (int n in time)
            {
                ans += n;
                if (ans % 10 != 0)
                {
                    ans += 10 - (ans % 10);
                }
            }
            Console.WriteLine(ans);
        }
    }*/
    //122B
    /*class Program
    {
        static void Main()
        {
            int anscount = 0;
            List<int> Answer = new List<int>();
            string S = Console.ReadLine();
            char[] Cstr = new char[S.Length];
            for (int i=0;i<S.Length;i++)
            {
                Cstr[i] = S[i];
            }
            for (int i=0;i<Cstr.Length;i++)
            {
                var temp = i;
                while (true)
                {
                    if (temp < Cstr.Length)
                    {
                        if (Cstr[temp] == 'A' || Cstr[temp] == 'C' || Cstr[temp] == 'G' || Cstr[temp] == 'T')
                        {
                            anscount++;
                            temp++;
                        }
                        else
                        {
                            Answer.Add(anscount);
                            anscount = 0;
                            break;
                        }
                    }
                    else
                    {
                        Answer.Add(anscount);
                        anscount = 0;
                        break;
                    }
                }
            }
            Console.WriteLine(Answer.Max());
        }
    }*/
    //122B
    /*class Program
    {
        static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int M = input[1];
            int C = input[2];
            int[] B  = Console.ReadLine().Split().Select(int.Parse).ToArray();
            List<int[]> AA = new List<int[]>();
            for (int i =0;i< N;i++)
            {
                int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
                AA.Add(a);
            }
            int Ans = 0;
            List<int> mans = new List<int>();
            for (int i =0;i<N;i++)
            {
                for (int j=0;j<M;j++)
                {
                    Ans += AA[i][j] * B[j];
                }
                var ans =Ans + C;
                mans.Add(ans);
                Ans = 0;
            }
            int count = 0;
            foreach (int n in mans)
            {
                if (n > 0)
                {
                    count++;
                }
            }
            Console.WriteLine(count);
        }
    }*/
    //120B
    /*class Program
    {
        static void Main()
        {
            List<int> Array1 = new List<int>();
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = input[0];
            int B = input[1];
            int K = input[2];
            int index = 1;
            List<int> a = new List<int>();
            a.Add(A);
            a.Add(B);
            var aa = a.Max();
            while (true)
            {
                if (A % index == 0 && B % index == 0)
                {
                    Array1.Add(index);

                    index++;
                }
                else 
                {
                    index++;
                }
                if (aa+1  == index)
                {
                    break;
                }
            }
            //配列逆になってない
            //100 100 1 100
            //16 16 4 2
            //16 16 3 4
            Array1.Sort();
            Array1.Reverse();
            Console.WriteLine(Array1[K-1]);
        }
    }*/
    //118B
    /*class Program
    {
        static void Main()
        {
            int Ans = 0;
            List<int[]> table = new List<int[]>();
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int M = input[1];
            int[] bb = new int[M];
            for (int i=0;i<N;i++)
            {
                var temp = Console.ReadLine().Split().Select(int.Parse).ToArray();
                table.Add(temp);
            }
            for (int i = 0; i < M; i++)
            {
                var ans = N;
                bb[i] = ans;
            }
            foreach (int[] n in table)
            {
                //初期化
                for (int i=1;i<n.Length;i++)
                {
                    bb[n[i]-1] = bb[n[i]-1]-1;
                }
            }
            for (int i = 0;i< bb.Length;i++)
            {
                if (bb[i] ==0)
                {
                    Ans++;
                }
            }
            Console.WriteLine(Ans);
        }
    }*/
    //119B
    /*class Data
    {
        public double Get { get; set; }
        public string Which { get; set; }
    }
    class Program
    {
        static void Main()
        {
            double Ans = 0;
            List<Data> table = new List<Data>();
            Data data;
            int N = int.Parse(Console.ReadLine());
            for (int i=0;i< N; i++)
            {
                data = new Data();
                var w = Console.ReadLine().Split();
                data.Get = double.Parse(w[0]);
                data.Which = w[1];
                table.Add(data);
            }
            foreach(Data nn in table)
            {
                if (nn.Which == "JPY")
                {
                    Ans += nn.Get;
                }
                else
                {
                    Ans += (nn.Get/1.0) * 380000.0;
                }
            }
            Console.WriteLine(Ans);
        }
    }*/
    //117B
    /*class Program
    {
        static void Main()
        {
            int ans = 0;
            int N = int.Parse(Console.ReadLine());
            int[] length = Console.ReadLine().Split().Select(int.Parse).ToArray();
            for (int i =0;i<length.Length;i++)
            {
                ans += length[i];
            }
            ans = ans - length.Max();
            if (length.Max() < ans)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }*/
    //116B
    /*class Progaram
    {
        static void Main()
        {
            int Ans = 0;
            int S = int.Parse(Console.ReadLine());
            List<int> Answer = new List<int>();
            int ans = S;
            Answer.Add(S);
            bool bunn = false;
            while (true)
            {
                if (ans %2 ==0)
                {
                    ans = ans / 2;
                    Answer.Add(ans);
                }
                else if (ans % 2 == 1)
                {
                    ans = 3 * ans + 1;
                    Answer.Add(ans);
                }
                for (int i=0;i<Answer.Count;i++)
                {
                    for (int j =i+1;j<Answer.Count;j++)
                    {
                        if (Answer[i] == Answer[j])
                        {
                            Ans = j;
                            bunn =true;
                        }
                    }
                }
                if (bunn)
                {
                    break;
                }
            }
            Console.WriteLine(Ans+1);
        }
    }*/
    //115B
    /*class Program
    {
        static void Main()
        {
            int Answer = 0;
            int N = int.Parse(Console.ReadLine());
            List<int> price = new List<int>();
            for (int i=0;i<N;i++)
            {
                var temp = int.Parse(Console.ReadLine());
                price.Add(temp);
            }
            price.Sort();
            price.Reverse();
            price[0] = price[0] / 2;
            foreach (int n in price)
            {
                Answer += n;
            }
            Console.WriteLine(Answer);
        }
    }*/
    //114B
    /*class Program
    {
        static void Main()
        {
            int an = 0;
            List<int> Answer = new List<int>();
            string S = Console.ReadLine();
            char[] temp = new char[S.Length];
            for (int i=0;i<S.Length;i++)
            {
                temp[i] = S[i];
            }
            for (int i=0;i<S.Length-2;i++)
            {
                var a = Convert.ToInt32(temp[i].ToString());
                var b = Convert.ToInt32(temp[i + 1].ToString());
                var c = Convert.ToInt32(temp[i + 2].ToString());
                an = a * 100 + b * 10 + c;
                var tempAns = Math.Abs(753 - an);
                Answer.Add(tempAns);
            }
            Console.WriteLine(Answer.Min());
        }
    }*/
    //112B
    /*class Program
    {
        static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int T = input[1];
            List<int[]> table = new List<int[]>();
            List<int[]> table2 = new List<int[]>();
            for (int i=0;i<N;i++)
            {
                var temp = Console.ReadLine().Split().Select(int.Parse).ToArray();
                table.Add(temp);
            }
            foreach (int[] time in table)
            {
                if (time[1] <= T)
                {
                    table2.Add(time);
                }
            }
            List<int> anss = new List<int>();
            foreach (int[] ans in table2)
            {
                anss.Add(ans[0]);
            }
            if (anss.Count == 0)
            {
                Console.WriteLine("TLE");

            }
            else
            {
                Console.WriteLine(anss.Min());
            }
        }
    }*/
    //111B
    /*class Program
    {
        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            while (true)
            {
                int hun = N / 100;
                int ten = N % 100 /10;
                int one = N % 10;
                if (hun == ten && ten == one && one == hun)
                {
                    break;
                }
                N++;

            }
            Console.WriteLine(N);
        }
    }*/
    //110B
    /*class Program
    {
        static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int M = input[1];
            int X = input[2];
            int Y = input[3];
            int counter = 0;
            int counter1 = 0;
            bool ans = false;
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] y = Console.ReadLine().Split().Select(int.Parse).ToArray();
            for (int i =0;i<y.Length;i++)
            {
                if (y[i] > X && y[i] <= Y)
                {
                    counter = 0;
                    for (int j = 0; j < x.Length; j++)
                    {
                        if (y[i] > x[j])
                        {
                            counter++;
                        }
                    }
                    if (counter == x.Length)
                    {
                        counter1 = 0;
                        for (int k = 0;k< y.Length;k++)
                        {
                            if (y[i] <= y[k])
                            {
                                counter1++;
                            }
                        }
                        if (counter1 == y.Length)
                        {
                            Console.WriteLine("No War");
                            ans = true;
                            break;
                        }
                    }
                }
            }
            if (ans == false)
            {
                Console.WriteLine("War");
            }
        }
    }*/
    //109B 
    /*class Program
    {
        static void Main()
        {
            List<string> Str = new List<string>();
            List<string> Str2 = new List<string>();
            List<char[]> oo = new List<char[]>();
            int N = int.Parse(Console.ReadLine());
            int koko = 0;
            bool te = false;
            bool kko = false;
            for (int i = 0; i < N; i++)
            {
                var str = Console.ReadLine();
                Str.Add(str);
            }
            foreach (string ans in Str)
            {
                char[] temp = ans.ToCharArray();
                oo.Add(temp);

                if (oo[temp.Length-1] == temp[0] || te == false)
                {
                    koko++;
                    var a = string.Join("", tempbefore).ToString();
                    var ss = string.Join("", temp).ToString();
                    Array.Copy(temp, tempbefore, temp.Length);
                    Str2.Add(a);
                    foreach (string nn in Str2)
                    {
                        if (a == nn)
                        {
                            kko = true;
                        }
                    }
                    if (kko == true)
                    {
                        break;
                    }
                    te = true;
                    Array.Copy(temp, tempbefore, temp.Length);
                }
                else
                {
                    break;
                }
            }
            if (koko == N-1)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }*/
    /*class Program
    {
        static void Main()
        {
            int count = 1;
            bool flag = false;
            List<string> strArray = new List<string>();
            int N = int.Parse(Console.ReadLine());
            for (int i =0;i<N;i++)
            {
                string input = Console.ReadLine();
                strArray.Add(input);
            }
            for (int a = 0;a<N;a++)
            {
                for (int i =a+1; i< N; i++)
                {
                    if (strArray[a] == strArray[i])
                    {
                        flag = true;
                    }
                }
            }
            if (flag == false)
            {
                for (int i = 0; i < N - 1; i++)
                {
                    //stringからchar[]
                    char[] temp = strArray[i].ToCharArray();
                    char[] temp1 = strArray[i + 1].ToCharArray();
                    if (temp[temp.Length - 1] == temp1[0])
                    {
                        count++;
                    }
                    else
                    {
                        flag = true;
                        break;
                    }
                }
                if (count == N)
                {
                    Console.WriteLine("Yes");
                }
                else
                {
                    Console.WriteLine("No");
                }
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }*/
    //108B
    /*class Program
    {
        static void Main()
        {
            List<int[]> ans = new List<int[]>();
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int X1 = input[0];
            int Y1 = input[1];
            int X2 = input[2];
            int Y2 = input[3];

            if (X1==X2)
            {
                if (Y1 > Y2)
                {
                    var X4 = X1 + Math.Abs(X1 - X2);
                    var Y4 = Y1;

                    var X3 = X1 + Math.Abs(X1 - X2);
                    var Y3 = Y2;
                    Console.WriteLine(X3 + " " + Y3 + " " + X4 + " " + Y4);
                }
                if (Y2 > Y1)
                {
                    var X4 = X1-Math.Abs(X1 - X2);
                    var Y4 = Y1;

                    var X3 = X1 - Math.Abs(X1 - X2);
                    var Y3 = Y2;
                    Console.WriteLine(X3 + " " + Y3 + " " + X4 + " " + Y4);
                }
            }
            if (Y1 == Y2)
            {
                /*var X4 = Math.Min(X1, X2); //Math.Abs(Y1 - Y2);
                var Y4 = Math.Abs(X1-X2);

                var X3 = Math.Max(X1,X2);
                var Y3 = Y4;
                Console.WriteLine(X3 + " " + Y3 + " " + X4 + " " + Y4);
                if (X1 > X2)
                {
                    var X4 = X1;
                    var Y4 = Y1 - Math.Abs(X1 - X2);

                    var X3 = X2;
                    var Y3 = Y2 - Math.Abs(X1 - X2);
                    Console.WriteLine(X3 + " " + Y3 + " " + X4 + " " + Y4);
                }
                if (X2 > X1)
                {
                    var X4 = X1 - Math.Abs(X1 - X2);
                    var Y4 = Y1;

                    var X3 = X1 - Math.Abs(X1 - X2);
                    var Y3 = Y2;
                    Console.WriteLine(X3 + " " + Y3 + " " + X4 + " " + Y4);
                }
            }
        }
    }*/
    //Contest131A
    /*class Program
    {
        static void Main()
        {
            bool flag = false;
            List<int> temp = new List<int>();
            string input = Console.ReadLine();
            for (int i = 0; i < input.Length; i++)
            {
                var a = Convert.ToInt32(input[i].ToString());
                temp.Add(a);
            }

            for (int i=0;i<input.Length-1;i++)
            {
                if (temp[i] == temp[i+1])
                {
                    flag = true;
                }
            }
            if (flag == true)
            {
                Console.WriteLine("Bad");
            }
            else
            {
                Console.WriteLine("Good");
            }
        }
    }*/
    //Contest131B
    /* class Program
     {
         static void Main()
         {
             int ans = 0;
             int mm = 0;
             int index = 0;
             int sum = 0;
             List<int> array = new List<int>();
             List<int> array1 = new List<int>();
             int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
             int N = input[0];
             int L = input[1];
             for (int i = 1;i<=N;i++)
             {
                 var azi = L + i - 1;
                 array.Add(azi);
             }
             for (int i=0;i<N;i++)
             {
                 sum += array[i];
             }
             for (int i=0;i<N;i++)
             {
                 var temp = Math.Abs(array[i]);
                 array1.Add(temp);
             }
             index = array1.IndexOf(array1.Min());
             for(int i=0;i<N;i++)
             {
                 if (i == index)
                 {
                     ans += 0;
                 }
                 else
                 {
                     ans += array[i];
                 }
             }
             Console.WriteLine(ans);
         }
     }*/
    //Contest131C
    /*class Program
    {
        static void Main()
        {

        }
    }*/
    //Contest131D&& ans % D != 0
    /*class Data
    {
        public int a { get; set; }
        public int b { get; set; }
    }
    class Program
    {
        static void Main()
        {
           
            List<Data> data = new List<Data>();
            List<int[]> ans = new List<int[]>();
            int N = int.Parse(Console.ReadLine());
            for (int i=0; i<N; i++)
            {
                var drr = new Data();
                int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
                drr.a = input[0];
                drr.b = input[1];
                data.Add(drr);
            }
            data = data.OrderBy(n => n.b).ToList();
            int Ans = 0;
            bool flag = false;
            foreach (Data aa in data)
            {
                Ans += aa.a;
                if (Ans > aa.b)
                {
                    flag = true;
                    break;
                }
            }
            if (flag)
            {
                Console.WriteLine("No");
            }
            else
            {
                Console.WriteLine("Yes");
            }
        }
    }*/
    //108B
    /*class Data
    {
        public List<string> Y { get; set; }
        public List<string> X { get; set; }
    }
    class Program
    {
        static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int H = input[0];
            int W = input[1];
            List<int> Y = new List<int>();
            List<int> X = new List<int>();
            //List<Data> griddata = new List<Data>();
            //Data data = new Data();
            List<char[]> temparray = new List<char[]>();
            for (int y = 0; y < H; y++)
            {
                var temp = Console.ReadLine().ToArray();
                temparray.Add(temp);
            }
            int count1 = 0;
            for (int i = 0; i < H; i++)
            {
                var num = 0;
                for (int j = 0; j < W; j++)
                {
                    num = i;
                    if (temparray[i][j] == '.')
                    {
                        count1++;
                    }
                }
                if (count1 == W) { Y.Add(num); }
                count1 = 0;
            }
            int count2 = 0;
            for (int i = 0; i < W; i++)
            {
                var num = 0;
                for (int j = 0; j < H; j++)
                {
                    num = i;
                    if (temparray[j][i] == '.')
                    {
                        count2++;
                    }
                }
                if (count2 == H) { X.Add(num); }
                count2 = 0;
            }
            //for (int i = 0; i < Y.Count; i++)
            for (int i = Y.Count-1; i >= 0; i--) 
            {
                temparray.RemoveAt(Y[i]);
            }
            for (int j = 0; j < X.Count; j++)
            {
                for (int i = 0; i < temparray.Count; i++)
                {
                    Array.Clear(temparray[i], X[j], 1);
                }
            }
            List<char[]> ko = new List<char[]>();
            int count = 0;
            var aa = new List<char>();
            foreach (char[] a in temparray)
            {
                foreach (char b in a)
                {
                    if (b != '\0')
                    {
                        
                        aa.Add(b);
                    }
                }
                foreach (char ji in aa)
                {
                    Console.Write(ji);
                }
                //ko.Add(mo);
                Console.Write('\n');
                aa.RemoveRange(0,aa.Count);
            }
        }
    }*/
    //105B
    /*class Program
    {
        static void Main()
        {
            int Ans = 0;
            int count = 0;
            int N = int.Parse(Console.ReadLine());
            for (int i = 1; i<=N;i++)
            {
                if (i % 2 == 1)
                {
                    for (int j = 1; j <= i; j++)
                    {
                        if (i % j == 0)
                        {
                            count++;
                        }
                    }
                    if (count == 8)
                    {
                        Ans++;
                    }
                    count = 0;
                }
            }
            Console.WriteLine(Ans);
        }
    }*/
    //104B
    //ApproaCh
    //AccccCcccc
    //AmvlkweClF
    //ATCoder
    /*class Program
    {
        static void Main()
        {
            bool flag = false;
            int count = 0;
            string S = Console.ReadLine();
            List<char> carray = new List<char>();
            foreach (char n in S)
            {
                carray.Add(n);
            }
            for (int i =0;i<carray.Count-1;i++) {
                if (carray[0] == 'A')
                {
                    if (2 <= i && i <= carray.Count - 1 && carray[i] == 'C')
                    {
                            count++;
                    }
                }
                else
                {
                    break;
                }
            }
            if (count == 1)
            {
                foreach (char m in carray)
                {
                    if (char.IsUpper(m))
                    {
                        if (m != 'C' && m != 'A')
                        {
                            flag = true;
                        }
                    }
                }
            }
            else { flag = true; }

            if (flag)
            {
                Console.WriteLine("WA");
            }
            else
            {
                Console.WriteLine("AC");
            }
        }
    }*/
    /*class Program
    {
        public static void Main()
        {
            string s = ReadLine();

            bool cond1 = (s[0] == 'A');

            int ct = 0, idx = -1;
            for (int i = 2; i < s.Length - 1; i++)
            {
                if (s[i] == 'C')
                {
                    ct++;
                    idx = i;
                }
            }

            bool cond2 = (ct == 1);

            bool cond3 = true;
            for (int i = 1; i < s.Length; i++)
            {
                if (i != idx && Char.IsUpper(s[i])){ cond3 = false; break; }
            }

            string ans = (cond1 && cond2 && cond3) ? "AC" : "WA";

            WriteLine(ans);
        }
    }*/

    //ABC103B
    /*class Program
    {
        static void Main()
        {
            string strS = Console.ReadLine();
            string strT = Console.ReadLine();
            List<char> S = new List<char>();
            List<char> T = new List<char>();
            if (strS.Length <= 100 && strS.Length >= 2 )
            {
                for (int i = 0; i < strS.Length; i++)
                {
                    S.Add(strS[i]);
                }
                for (int i = 0; i < strT.Length; i++)
                {
                    T.Add(strT[i]);
                }
                S.Sort();
                T.Sort();
                String SS = new string(S.ToArray());
                String TT = new string(T.ToArray());

                if (SS.Equals(TT))
                {
                    Console.WriteLine("Yes");
                }
                else
                {
                    Console.WriteLine("No");
                }
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }*/
    /*class Program
    {
        static void Main()
        {
            bool flag = false;
            string S = Console.ReadLine();
            string T = Console.ReadLine();
            for (int i = 0;i<S.Length;i++)
            {
                var SS = S[S.Length - 1] + S.Substring(0, S.Length - 1);
                S = SS;
                if (S.Equals(T))
                {
                    flag = true;
                    break;
                }
            }
            if (flag)
            {
                Console.WriteLine("Yes");
            }
            else {
                Console.WriteLine("No");
            }
        }
    }*/
    //ABC101B
    /*class Program
    {
        static void Main()
        {
            int Answer = 0;
            string input = Console.ReadLine();
            int N = int.Parse(input);
            for (int i =0;i<input.Length;i++)
            {
                Answer += Convert.ToInt32(input[i].ToString());
            }
            if (N % Answer == 0)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }*/
    //ABC100B
    /*class Program
    {
        static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int D = input[0];
            int N = input[1];
            int Answer = 0;
            List<int> ans = new List<int>();
            switch(D)
            {
                case 0:
                    if (N != 100)
                    {
                        for (int i = 0; i <= 100; i++)
                        {
                            ans.Add(i);
                        }
                        Answer = ans[N];
                    }
                    else
                    {
                        Answer = 101;
                    }
                    break;

                case 1:
                    if (N != 100)
                    {
                        var mm = 1;
                        while (true)
                        {
                            var aa = 100 * mm;
                            ans.Add(aa);
                            if (mm == N + 1)
                            {
                                break;
                            }
                            mm++;
                        }
                        Answer = (mm - 1) * 100;
                    }
                    else
                    {
                        Answer = 10100;
                    }
                    break;

                case 2:
                    if (N != 100)
                    {
                        var mmm = 1;
                        while (true)
                        {
                            var aa = 100 * 100 * mmm;
                            ans.Add(aa);
                            if (mmm == N + 1)
                            {
                                break;
                            }
                            mmm++;
                        }
                        Answer = (mmm - 1) * 100 * 100;
                    }
                    else
                    {
                        Answer = 1010000;
                    }
                    break;
            }
            Console.WriteLine(Answer);
        }
    }*/
    //ABC99B
    /*class Program
    {
        static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int a = input[0];
            int b = input[1];
            List<int> str = new List<int>();
            int height = 0;
            for (int i=1;i<1000;i++)
            {
                for (int j=0;j<=i;j++)
                {
                    height += j;
                }
                str.Add(height);
                height = 0;
            }
            int ans = 0;
            var an = b - a;
            for (int i =0;i<998;i++)
            {
                if (Math.Abs(str[i] - str[i+1]) == an)
                {
                    //Console.WriteLine(str[i] + " " +str[i + 1]);
                    ans = str[i]-a;
                }
            }
            Console.WriteLine(ans);
        }
    }*/
    //ABC98B
    /*class Program
    {
        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            string S = Console.ReadLine();
            List<int> ans = new List<int>();
            int countX = 0;
            for (int i = 1; i<N;i++)
            {
                var X = S.Substring(0,i);
                var Y = S.Substring(i);
                int cnt = X.Where(a => Y.Contains(a)).Distinct().Count();
                countX = Math.Max(countX, cnt);
                /*for (char m = 'a'; m < 'z'; m++)
                {
                    if (X.Contains(m) && Y.Contains(m))
                    {
                        countX++;
                    }
                }
                ans.Add(countX);
                countX = 0;*/

                /*List<char> XX = new List<char>();
                for (char m = 'a'; m < 'z'; m++)
                {
                    if (X.Contains(m))
                    {
                        XX.Add(m);
                    }
                }
                foreach (char a in XX)
                {
                    if (Y.Contains(a))
                    {
                        countX++;
                    }
                    else {

                    }
                }
                ans.Add(countX);
                countX = 0;
            }
            Console.WriteLine(countX);
        }
    }*/
    //ABC97B
    class Program
    {
        static void Main()
        {
            int X = int.Parse(Console.ReadLine());
            int num = 2;
            double Ans = 0;
            List<double> Answer = new List<double>();
            if (X != 1)
            {
                while (num < X)
                {
                    int num2 = 2;
                    while (true)
                    {
                        var ans = Math.Pow(num, num2);
                        if (ans >= X)
                        {
                            if (num2 - 1 == 1)
                            {
                                break;
                            }
                            else if (ans == X)
                            {
                                Ans = ans;
                            }
                            else
                            {
                                Ans = Math.Pow(num, (num2 - 1));
                                Answer.Add(Ans);
                                break;
                            }
                        }
                        num2++;
                    }
                    num++;
                }
                Console.WriteLine(Answer.Max());
            }
            else
            {
                Console.WriteLine("1");
            }
        }
    }
}


Measured memory_bytes: 13268