//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
// int a = t.nextInt();
// for(int i=1; i<=a; i++) {
// System.out.print("*");
// }
// }
//}
//import java.util.*;
//
//public class Main {
//public static void main(String[] args) {
//
//
// Scanner t = new Scanner(System.in);
//
// int a = t.nextInt();
// int b = t.nextInt();
//
// for (int i=a; i<=b; i++) {
//
// if (i%2==1) {
// System.out.print(i+" ");
// }
//
// }
// }
//}
//
//
//import java.util.*;
//public class Main{
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int a = t.nextInt();
// int sum= 0;
//
// for (int i=1; i<=a; i++) {
// sum= sum+i;
//
// }
// System.out.println(sum);
//
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int a = t.nextInt();
// int sum = 0;
//
// for (int i=1; i<=a; i++) {
// if (i%2==0) {
// sum = sum+i;
// }
// }
// System.out.println(sum);
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
// int sum = 0;
// for (int i=1; i<=n; i++) {
// int a = t.nextInt();
// sum = sum+a;
// }
// System.out.println(sum);
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
// int sum = 0;
// for (int i=1; i<=n; i++) {
// int a = t.nextInt();
//
// if (a%5==0) {
// sum = sum + a;
// }
// }
// System.out.println(sum);
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
// int sum = 0;
//
// for (int i=1; i<=n; i++) {
// int a = t.nextInt();
//
// if (a%2==0) {
// sum = sum +1;
// }
// }
// System.out.println(sum);
// }
//}
//import java.util.*;
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
// int max = 0;
// for(int i=0; i<n; i++) {
// int a = t.nextInt();
//
// if(max < a) {
// max = a;
// }
// }
// System.out.println(max);
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int max = -1000000;int min = 1000000;
// for(int i=0; i<5; i++) {
// int a = t.nextInt();
//
// if(max < a) {
// max = a;
// }
// if (min > a) {
// min = a;
// }
// }
// System.out.println(max);
// System.out.println(min);
//
// }
//}
//
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
//
// for (int i=2; i<=n/2; i++) {
// if (n%i==0) {
// int k = i;
// int p = n/i;
//
// int kCnt = 0;
// int pCnt = 0;
// for(int j=1; j<=k; j++) {
// if(k%j==0) {
// kCnt++;
// }
// }
//
// for (int b=1; b<=p; b++) {
// if (p%b==0) {
// pCnt++;
// }
// }
//
// if(kCnt == 2 && pCnt == 2) {
// if (p>k) {
// System.out.println(k+" "+p);
// return ;
// }
// else if (k>p) {
// System.out.print(p+" "+k);
// return ;
// }
// }
// }
// }
// System.out.println("wrong number");
// }
//}
//import java.util.*;
//
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
//
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; j++) {
// System.out.printf("(%d %d)\t", i, j);
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//
//
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
//
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; j++) {
// if(i==i) {
// System.out.print("*");
// }
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//public class Main{
// public static void main(String[] args) {
// Scanner t= new Scanner(System.in);
//
// int n = t.nextInt();
//
// for (int i=0; i<n; i++){
// for (int j=0; j<n; j++) {
// if (i==0||i==n-1||j==0||j==n-1) {
// System.out.print("*");
// }
// else {
// System.out.print(" ");
// }
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//public class Main{
// public static void main(String[] args) {
// Scanner t= new Scanner(System.in);
//
// int n = t.nextInt();
//
// for (int i=0; i<n; i++){
// for (int j=0; j<n; j++) {
// if (i==0||i==n-1||j==0||j==n-1||i==j||j+i==n-1) {
// System.out.print("*");
// }
// else {
// System.out.print(" ");
// }
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
//
// for (int i=0; i<n; i++) {
// for (int j=0; j<n; j++) {
// if (i==0||i==n-1||j==0||j==n-1||i==j||j+i==n-1||j==(n-1)/2||i==(n-1)/2) {
// System.out.print("*");
// }
// else {
// System.out.print(" ");
// }
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
//
// for (int i=0; i<n; i++) {
// for (int j=0; j<=i; j++) {
// System.out.print("*");
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
//
// for (int i=0; i<n; i++) {
// for (int j=i; j<n; j++) {
// System.out.print("*");
// }
// System.out.println();
// }
// }
//}
//import java.util.*;
//public class Main {
// public static void main(String[] args) {
// Scanner t = new Scanner(System.in);
//
// int n = t.nextInt();
//
// for (int i=n-1; i>=0; i--) {
// for (int j=i; j<n-1;j++) {
// System.out.print(" ");
// }
// for (int j=i; j>=0; j--) {
// System.out.print("*");
// }
// System.out.println();
// }
// }
//}