public class Main {
    public static void main(String[] args) {
      //根据规律可知，即算出该数的二进制表示的位数
      //比如5，二进制表示为101，位数为3，则最少操作次数为3
        Scanner input=new Scanner(System.in);
        int t=input.nextInt();
        int[] a=new int[t];
      //循环遍历输入
        for (int i=0;i<t;i++) {
            a[i]=input.nextInt();
        }
        int[] res=zhao(a);  //调用方法得到结果
      //循环遍历输出
        for(int i=0;i<res.length;i++){
            System.out.println(res[i]);
        }
    }

    public static int[] zhao(int[] a){
        int[] b=new int[a.length];  //新建数组接住结果
      //遍历获取结果
        for(int i=0;i<b.length;i++){
          //数字转二进制字符串
            String temp=Integer.toBinaryString(a[i]);
          //获取每个数字的最少次数(字符串长度)
            b[i]=temp.length();
        }
        return b;
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int nums = sc.nextInt();
        for (int i = 0; i<nums; i++){
            int N = sc.nextInt();
            maxandmin(N);
        }
    }
  
    public static void maxandmin(int N){
        if (N==1||N==2){
            System.out.println("1 1");  //如果n是1或者2就输出 1 1
            return;
        }
        //之后每4个一组 0011
        int min = getmin(N);
        int max = N-getmin(N-1);
        System.out.println(min + " " + max);
    }
  
    public static int getmin(int N){
        int temp = (N-2)%4; //temp临时值接住
        if (temp==1 || temp==2){
            return 0;
        }
        else return 1;
    }
  
}

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n=input.nextInt();  //n个a
        int m=input.nextInt();  //m个b
        int k=input.nextInt();  //第k小的单词
        System.out.println(dik(n,m,k));
    }

    public static String dik(int n,int m,int k){
        String res="123";

        return res;
    }

}

public static int findRepeatNumber(int[] nums) {
       int res=0;
       Set<Integer> set=new HashSet<>();
       Arrays.sort(nums);  //排序
       for(int i=0;i<nums.length;i++){
           if(set.contains(nums[i])){
               return nums[i];  /如果出现过就弹出这个值
           }else{
               set.add(nums[i]);  //没出现过就添加到set里面
           }
       }
       return 0;
   }

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int[][] a=new int[][]{
                {1,4,7,11,15},
                {2,5,8,12,19},
                {3,6,9,16,22},
                {10,13,14,17,24},
                {18,21,23,26,30}
        }; 
        int target=input.nextInt();
        System.out.println(findNumberIn2DArray(a,target));
    }

    public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int hang=0; //从第一行开始
        int lie=matrix[0].length-1; //从最后一列开始
        while(hang<matrix.length&&lie>=0){
            if(matrix[hang][lie]==target){
                return true;  //找到了就返回true
            }else if(matrix[hang][lie]>target){
                lie--;   //这行后面都大 所以换前一列lie--   
            }else if(matrix[hang][lie]<target){
                hang++;  //这列上面都小 所以换下一行hang++
            }
        }
        return false; //默认找不到false
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s=input.nextLine();  //一定要用nextLine()  因为字符串有空格!!!!!!
        System.out.println(replaceSpace(s)); //调用方法返回结果
    }

    public static String replaceSpace(String s) {
        StringBuilder sb=new StringBuilder();  //新建sb对象
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i); //获取字符串每个位置字符
            if(c==' '){
                sb.append('%');  //遇到空格就分别添加 % 2 0
                sb.append('2');
                sb.append('0');
            }else{
                sb.append(c);  //不是空格就按序添加进去
            }
        } 
        return sb.toString(); //sb对象要转成字符串输出
    }

}

//定义好的链表类
  public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { 
		val = x; 
	  }
  }
 

//实现类
public class LianBiao {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        ListNode head=new ListNode(1);
        ListNode l2=new ListNode(3);
            head.next=l2;  // 1 -> 3
        ListNode l3=new ListNode(2);
            l2.next=l3;   // 1 -> 3 -> 2
        System.out.println(Arrays.toString(reversePrint(head)));
    }

    public static int[] reversePrint(ListNode head) {
      //栈存储链表所有元素
        Stack<ListNode> stack=new Stack<ListNode>();
      //按需存储压栈
        while(head!=null){
            stack.push(head);  //不断地压入栈
            head=head.next;
        }
      //结果返回到int数组
        int size=stack.size(); //获取stack栈的长度
        int[] a=new int[size]; //后面才能确定长度
        for (int i = 0; i < size ; i++) {
            a[i]=stack.pop().val;  //依次弹出
        }
        return a; //返回数组元素
    }

}

class CQueue {
    Deque<Integer> stack1;  //创建两个stack栈
    Deque<Integer> stack2;
    
    public CQueue() {
        stack1 = new LinkedList<Integer>();
        stack2 = new LinkedList<Integer>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);  //压栈
    }
    
    public int deleteHead() {
        // 如果第二个栈为空
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop()); //把stack1压入stack2
            }
        } 
        if (stack2.isEmpty()) {
            return -1;   //stack2为空 返回-1
        } else {
            int deleteItem = stack2.pop(); 
            return deleteItem;  //stack2不为空 出栈
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        System.out.println("递归:"+fib(n));
        System.out.println("动态规划:"+fiber(n));
    }

	//递归
    public static int fib(int n) {
        if(n<=1){
            return n;  // 0 1
        }
        if(n==2){
            return 1;  // 0 1 1
        }
        return (fib(n-1)+fib(n-2))%1000000007;
    }

	//动态规划
    public static int fiber(int n) {
        int a=0; //第一个值
        int b=1; //第二个值
        int c=0; //第三个值
        //不断迭代
        for(int i=0;i<n;i++){
            c=(a+b)%1000000007; //每次计算都要取余
            a=b;
            b=c;
        }
        return a;
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        /*for (int i = 0; i < n; i++) {
            a[i]=input.nextInt();
        }*/
        System.out.println("递归:"+numWays(n));
        System.out.println("动态规划:"+numWayser(n));
    }

    public static int numWays(int n) {
        if(n<=1){
            return 1;  // 1 1
        }
        if(n==2){
            return 2;  // 1 1 2
        }
        return (numWays(n-1)+numWays(n-2))%1000000007;
    }

    public static int numWayser(int n) {
        int a=1; //跳1个台阶 1
        int b=1; //跳1个台阶 1
        int c=0; //跳2个台阶 2
        //不断迭代
        for(int i=0;i<n;i++){
            c=(a+b)%1000000007; //每次计算都要取余
            a=b;
            b=c;
        }
        return a;
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for (int i = 0; i < n; i++) {
            a[i]=input.nextInt();
        }
        System.out.println(minArray(a));
    }

	//排序输出
    public static int minArray(int[] numbers) {
        Arrays.sort(numbers);  //排序
        return numbers[0];  //输出最小的第一位
    }

	//二分法
	public static int minArray(int[] numbers) {
        int i=0;  //左指针
        int j=numbers.length-1;  //右指针
        while(i<j){
            int z=(i+j)/2; //找中间位置
            if(numbers[z]>numbers[j]){
                i=z+1;   //min值在右边出现
            }else if(numbers[z]<numbers[j]){
                j=z;    //min值在左边出现
            }else {
                j--;    //无法确定范围 缩小范围继续找
            }
        }
        return numbers[i];
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        char[][] a= new char[][]{   //定义好要找的路径集
                {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','E'}};      
        String word=input.next();  //输入要找的路径
        System.out.println(exist(a,word)); //调用方法
    }

    public static boolean exist(char[][] board, String word) {
        char[] words=word.toCharArray(); //字符串转字符数组
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(dfs(board, words, i, j, 0)) {
                    return true;  //二重循环调用方法
                }
            }
        }
        return false; //默认失败
    }

    //board是要找的路径集合  words字符串转的字符数组  i和j是board下标  k是找到了几个
    private static boolean dfs(char[][] board, char[] words, int i, int j, int k) {
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != words[k]){
            return false;  // i和j越界 / 找不到符合
        }
        if(k == words.length - 1) {  //已经全部找到了!!!
            return true;
        }
        char temp=board[i][j]; //中间值
        board[i][j]='/'; //用过之后改成 ‘/’
		//上下左右都找找
        boolean res=dfs(board, words, i + 1, j, k + 1) || dfs(board, words, i - 1, j, k + 1) ||
                dfs(board, words, i, j + 1, k + 1) || dfs(board, words, i , j - 1, k + 1);
        board[i][j]=temp; //用完之后再回溯返回原值
        return res;
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int m=input.nextInt();
        int n=input.nextInt();
        int k=input.nextInt();
        System.out.println(movingCount(m,n,k));
    }

    public static int movingCount(int m, int n, int k) {
        int res=123;
        return res;
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int m=input.nextInt();
        System.out.println(cuttingRope(m));
    }

    public static int cuttingRope(int n) {
        if(n<=3){
            return n-1;
        }
        int a=n/3;
        int b=n%3;
        if(b==0){
            return (int)Math.pow(3,a);
        }
        if(b==1){
            return (int)Math.pow(3,a-1)*4;
        }
        return (int)Math.pow(3,a)*2;
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int m=input.nextInt();
        System.out.println(cuttingRope(m));
    }

    public static int cuttingRope(int n) {
		//把其他特定条件列出
        if(n==2){
           return 1; //分为1 1
        }
        if(n==3){
           return 2; //分为1 2 
        }
        if(n==4){
           return 4; //分为2 2
        }
        if(n<4){
           return n-1;  //如果长度<4 返回 1 3
        }
        long res=1;  //最终结果
        int mod=1000000007;
        while(n>4){
            res=res*3; //不停地乘3
            res=res%mod; //然后取余 (防止溢出)
            n=n-3;  //每次使用完减去3
        }
        res=res*n; //乘上剩下的n  (最后剩下的肯定是4 3 2 这三种情况就直接乘n即可)
        res=res%mod;  //不要忘记取余
        return (int)res; //返回最后res
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int m=input.nextInt();
        System.out.println(hammingWeight(m));
    }

    public static int hammingWeight(int n) {
        int res=0; //接最后结果
        while(n!=0){
            res++; 
            n=n&(n-1);  //消除数字n最右边的1
        }
        return res;
    }

}

public class DelJie {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        ListNode head=new ListNode(4);
        ListNode l2=new ListNode(5);
        head.next=l2;  // 4 -> 5
        ListNode l3=new ListNode(1);
        l2.next=l3;    // 4 -> 5 -> 1
        ListNode l4=new ListNode(2);
        l3.next=l4;    // 4 -> 5 -> 1 -> 9
        int val=input.nextInt(); //输入要删除的节点
    }

    public static ListNode deleteNode(ListNode head, int val) {
        if(head==null){  //如果链表为空返回null
            return null;
        }
        if(head.val==val){  //如果当前节点就是要删除的
            return head.next;  //返回head.next就行
        }
        ListNode temp=head;  //head节点给一个临时temp节点
        while(temp.next!=null){
            if(temp.next.val==val){    //如果下一个节点是要删除的节点
                temp.next=temp.next.next;  //直接这个节点的下一个节点连接下下一个节点(跳过要删除的节点)
            }else{
                temp=temp.next;  //不是的话就继续下一个节点
            }
        }
        return head;  //返回原节点
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s=input.next();  //输入s
        String p=input.next();  //输入p
        System.out.println(isMatch(s,p));  //调用方法
    }

    public static boolean isMatch(String s, String p) {
        int n=s.length();  //获取s的长度
        int m=p.length(); //获取p的长度
        boolean[][] f=new boolean[n+1][m+1];  //获取结果(多一位方便取)
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
            //空正则
                if (j==0){  //要判断的p字符串为空
                    f[i][j]=i==0;
                }
            //非空正则
                else{
                    //分为 * 和 非*
                    if(p.charAt(j-1)!='*'){
                        //两个倒数第二位一样 p的倒数第二位还是.
                        if(i>0&&(s.charAt(i-1)==p.charAt(j-1)||p.charAt(j-1)=='.')){
                            f[i][j]=f[i-1][j-1];
                        }
                    }
                    else{
                        //不看*之前的内容
                            if(j>=2){
                                f[i][j]|=f[i][j-2];  //直接砍掉p的后面两个
                            }
                        //看*之前的内容
                        if (i >= 1 && j >= 2 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {
                            f[i][j] |= f[i - 1][j];  //s串前移一个
                        }
                    }
                }

            }
        }
        return f[n][m];  //返回当前位置结果
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s=input.next();
        System.out.println(isNumber(s));
    }

    public static boolean isNumber(String s) {
            if(s==null||s.length()==0) {
                return false;  //字符串为空格
            }
            boolean numSeen=false;  //出现数字
            boolean dotSeen=false;  //出现 .
            boolean eSeen=false;    //出现 e/E
            char arr[]=s.trim().toCharArray(); //转字符数组(去除空格
            for(int i=0; i<arr.length; i++){
                if(arr[i]>='0'&&arr[i]<='9'){  //数字
                    numSeen=true;  //更改为true
                }
                else
                    if(arr[i]=='.'){  // .
                        if(dotSeen||eSeen){ //在这个.之前有 . / e/E就false (举例: . . / e .)
                            return false; //在这个.之前有数字没啥影响( 举例:123. )
                        }
                        dotSeen=true;  //更改为true
                    }
                    else
                        if(arr[i]=='E'||arr[i]=='e'){  // e/E
                            if(eSeen||!numSeen){
                                return false;  //在这个之前没有数字 / . 就false
                            }
                            eSeen=true;  //更改为true
                            numSeen=false; //设置成false防止e/E后面没有数字
                        }
                        else
                            if(arr[i]=='+'||arr[i]=='-'){  // + / -
                                if(i!=0&&arr[i-1]!='e'&&arr[i-1]!='E'){  // 不是第一位出现 / 前一个不是e/E
                                    return false;
                                }
                            }
                            else{  //其他情况
                                    return false; //其他情况都是false
                            }
            }
            return numSeen;  //返回数字属性
        }

}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for (int i = 0; i < a.length; i++) {
            a[i]=input.nextInt();
        }
        System.out.println(Arrays.toString(exchange(a)));
    }

    public static int[] exchange(int[] nums) {
       int i=0; //左指针
       int j=nums.length-1;  //右指针
       int temp=0; //临时交换用
       while(i<j) {
           while (i < j && ((nums[i] % 2) != 0)) {
               i++; //奇数往后移动
           }
           while (i < j && ((nums[j] % 2) == 0)) {
               j--; //偶数往前移动
           }
           //左边是偶数 右边是奇数的话就交换
            temp = nums[i];
           nums[i] = nums[j];
            nums[j] = temp;
       }
       return nums;
    }

}

public class DaoShuK {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        ListNode head=new ListNode(4);
        ListNode l2=new ListNode(5);
        head.next=l2;  // 4 -> 5
        ListNode l3=new ListNode(1);
        l2.next=l3;    // 4 -> 5 -> 1
        ListNode l4=new ListNode(2);
        l3.next=l4;    // 4 -> 5 -> 1 -> 9
        int k=input.nextInt(); //输入要查看的倒数第k个节点
        System.out.println(getKthFromEnd(head,k));
    }

    public static ListNode getKthFromEnd(ListNode head, int k) {
        ListNode former = head, latter = head;  //初始化两个指向头节点head的链表
    // 假设5个数字 求倒数第二个(正数第四个) 5-2+1=4
        for(int i = 0; i < k; i++) {
            if(former == null) return null;
            former = former.next;  //先让former提前走k步
        }
    // former走了2步 现在在第二个数位置    
        while(former != null) {
            former = former.next;  //一起走了3步之后
            latter = latter.next; //latter到了倒数第k个值得位置
        }
        return latter;  //返回latter链表
    }

}

public class DaoShuK {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        ListNode head=new ListNode(4);
        ListNode l2=new ListNode(5);
        head.next=l2;  // 4 -> 5
        ListNode l3=new ListNode(1);
        l2.next=l3;    // 4 -> 5 -> 1
        ListNode l4=new ListNode(2);
        l3.next=l4;    // 4 -> 5 -> 1 -> 9
        System.out.println(reverseList(head));
    }

    public static ListNode reverseList(ListNode head) {
      //新建栈存链表元素
        Stack<Integer> stack = new Stack<Integer>();
      //新建tmp链表用来将head存入栈
        ListNode tmp = head;
        while(tmp!=null){
            stack.push(tmp.val);  //压栈
            tmp = tmp.next; //链表往后移
        }
      //因为已经用完了所以重新指向head
        tmp = head;
        while(tmp!=null){
            tmp.val = stack.pop();  //出栈
            tmp = tmp.next; //链表往后移动
        }
        return head; //因为之前把head位置的值改了就从head输出即可
    }

}

public class DaoShuK {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
    //第一个链表l1
        ListNode l1=new ListNode(1);
        ListNode l12=new ListNode(2);
        l1.next=l12;  // 1 -> 2
        ListNode l13=new ListNode(4);
        l12.next=l13;    // 1 -> 2 -> 4
    //第二个链表l2
        ListNode l2=new ListNode(1);
        ListNode l22=new ListNode(3);
        l2.next=l22;   // 1 -> 3
        ListNode l23=new ListNode(4);
        l22.next=l23;    // 1 -> 3 -> 4
    //调用方法返回结果
        System.out.println(mergeTwoLists(l1,l2));
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null){  //l1链表为空
            return l2;  //直接返回l2链表
        }
        if(l2==null){   //l2链表为空
            return l1;  //直接返回l1链表
        }
        ListNode l3=new ListNode(0); //前置伪头节点(只是为了连起来)
        ListNode cur=l3;
        while(l1.next!=null&&l2.next!=null){
            if(l1.val>l2.val){
                cur.next=l2;
                l2=l2.next;
            }else{
                cur.next=l1;
                l1=l1.next;
            }
            cur=cur.next;
        }
        //跳出while肯定是有一个为空
        if(l1.next!=null){
           cur.next=l1.next;
        }else{
            cur.next=l2.next;
        }
        return l3.next; //第一个位置是伪头节点
    }

}

/**
 * 定义树类:
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public static boolean isSubStructure(TreeNode A, TreeNode B) {
      // A/B结束了还没找到
        if(A == null || B == null){
            return false;
        }
      //是一部分
        if(isPartSame(A,B)){
            return true;
        }else{
            //不是一部分  去找左节点或者右节点
            return isSubStructure(A.left,B)||isSubStructure(A.right,B);
        }
    }

	//判断是不是存在的一部分!
    public static boolean isPartSame(TreeNode A, TreeNode B) {
        if(B==null){
            return true;  //已经找完了
        }
        if(A==null){
            return false;  //还没找完A没了
        }
        if(A.val==B.val){  //当前节点找到了 找下面的节点(递归)
            return isPartSame(A.left,B.left) && isPartSame(A.right,B.right);
        }else{
            return false; //节点都不相同
        }
    }
}

//1.递归
public static TreeNode mirrorTree(TreeNode root) {
        if(root==null){
            return null;  //如果root为空 返回空
        }
        TreeNode leftRoot = mirrorTree(root.right);  //递归交换当前节点的右节点
        TreeNode rightRoot = mirrorTree(root.left);  //递归交换当前节点的左节点
        root.left = leftRoot;    //两个交换
        root.right = rightRoot;
        return root;
    }

public static boolean isSymmetric(TreeNode root) {
        //方法调用
        return isSymmetric(root,root);
    }

    public static boolean isSymmetric(TreeNode root1,TreeNode root2){
        if(root1 == null && root2 == null){
            return true;  //空树
        }
        //只有一个子结点
        if(root1 == null || root2 == null){
            return false;  //肯定不对称
        }
        //有两个子节点 但是值不相同
        if(root1.val != root2.val){
            return false;
        }
        //递归调用
        return isSymmetric(root1.left, root2.right) && isSymmetric(root1.right,root2.left);
    }

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int[][] a=new int[][]{{1,2,3},{4,5,6},{7,8,9}};
        System.out.println(Arrays.toString(spiralOrder(a)));
    }

    public static int[] spiralOrder(int [][] matrix) {
        if(matrix.length == 0) {
            return new int[0];  //数组空就弹出空数组
        }
        int row=matrix.length;     //行
        int col=matrix[0].length;  //列
        int left=0;   //二维数组上面行的最左边
        int right=col-1; //二维数组上面行的最右边
        int top=0;   //二维数组左边的最上边
        int bottom=row-1;  //二维数组左边的最下边
        int[] a=new int[row*col];
        int q=0; //控制结果数组下标
        while(left<=right&&top<=bottom){
            //从左到右
            for(int i=left;i<=right;i++){
                a[q++]=matrix[top][i];  //top行
            }
            //从上到下(从下一行开始向下走)
            for(int i=top+1;i<=bottom;i++){
                a[q++]=matrix[i][right]; //right列
            }
            //从右到左(从左边一列开始向左走)
            if(top!=bottom) {   //如果是一行的话就不需要返回去(已经左到右)
                for (int i=right-1;i>=left;i--) {
                    a[q++]=matrix[bottom][i]; //bottom行
                }
            }
            //从下到上(从上一行开始向上走)
            if(left!=right) {  //如果是一列的话就不需要返回去(已经上到下)
                for (int i=bottom-1;i>top;i--) {
                    a[q++]=matrix[i][left];  //left列
                }
            }
            //下一个正方形矩阵(往里缩小 -- 变换四个下标)
                top++;
                right--;
                left++;
                bottom--;
        }
        return a;  //返回a数组
    }

}

class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int[] a=new int[]{1,2,3,4,5};  //压栈
        int[] b=new int[]{4,5,3,2,1};  //压栈的一种出栈可能
        System.out.println(validateStackSequences(a,b));
    }

    public static boolean validateStackSequences(int[] pushed, int[] popped) {
      //生成新的栈(尝试模拟)
        Stack<Integer> stack=new Stack<Integer>();
        int count=0;
        for(int i=0;i<pushed.length;i++){
            stack.push(pushed[i]);  //按照pushed数组入栈
            while(!stack.isEmpty()&&stack.peek()==popped[count]){  //栈顶值==出栈的当前位置
                stack.pop(); //出栈
                count++;  //后移(判断下一位出栈)
            }
        }
        return stack.empty(); //是否所有都出栈(归0)
    }

}

public class ErChaShu {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(3); //根节点3
        TreeNode r1=new TreeNode(9);
        	root.left=r1;
        TreeNode r2=new TreeNode(20);
        	root.right=r2;
        TreeNode r21=new TreeNode(15);
        	r2.left=r21;
        TreeNode r22=new TreeNode(7);
        	r2.right=r22;
        System.out.println(Arrays.toString(levelOrder(root)));
    }

    public static int[] levelOrder(TreeNode root) {
        //空树
            if(root==null){
                return new int[0]; //返回空
            }
        //新建队列
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);  //先将root放入
        //新建list集合(存放读取顺序)
            List<Integer> list=new ArrayList<>();
            while(!queue.isEmpty()){  //当queue为空就弹出 (所有节点都取出)
                TreeNode temp=queue.poll(); //弹出当前节点
                list.add(temp.val); //list集合接住当前节点的值
                if(temp.left != null)
                    queue.add(temp.left);  //队列添加左节点
                if(temp.right != null)
                    queue.add(temp.right);  //队列添加右节点
            }
        //新建res数组用于存储结果
            int[] res=new int[list.size()] ;
            for (int i = 0; i < res.length; i++) {
                    res[i]=list.get(i);  //遍历放入数组
            }
            return res;
    }

}

public class ErChaShu {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(3); //根节点3
        TreeNode r1=new TreeNode(9);
            root.left=r1;
        TreeNode r2=new TreeNode(20);
            root.right=r2;
        TreeNode r21=new TreeNode(15);
            r2.left=r21;
        TreeNode r22=new TreeNode(7);
            r2.right=r22;
        //返回list集合先转数组toArray() 然后Arrays.toString()转字符串输出
            System.out.println(Arrays.toString(levelOrder(root).toArray()));
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
      //空树
        if(root==null){
            return new ArrayList<>();
        }
      //新建队列存储每个节点(<>里面是treenode)
        Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root); //先存入root根节点
      //存储最终结果res集合
        List<List<Integer>> res=new ArrayList<>();
        while(!queue.isEmpty()) {  //最后队列是否为空(用完了)
            List<Integer> temp = new ArrayList<>();
            for (int i=queue.size();i>0;i--) {
                TreeNode t = queue.poll();  //出队
                temp.add(t.val);  //将弹出的节点的值放入temp队列
                if (t.left != null) {
                    queue.add(t.left); //刚才要弹出节点的左节点入队
                }
                if (t.right != null) {
                    queue.add(t.right); //刚才要弹出节点的左节点入队
                }
            }
            res.add(temp);  //每一层的temp加入到list最终集合
        }

        return res;
    }

}

public class ErChaShu {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(3); //根节点3
        TreeNode r1=new TreeNode(9);
            root.left=r1;
        TreeNode r2=new TreeNode(20);
            root.right=r2;
        TreeNode r21=new TreeNode(15);
            r2.left=r21;
        TreeNode r22=new TreeNode(7);
            r2.right=r22;
        //返回list集合先转数组toArray() 然后Arrays.toString()转字符串输出
            System.out.println(Arrays.toString(levelOrder(root).toArray()));
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
      //空树
        if(root==null){
            return new ArrayList<>();
        }
      //新建队列(存储节点)
        Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root); //先存入root根节点
      //新建嵌套list集合存储最终结果
        List<List<Integer>> res=new ArrayList<>();
      //新建计数器(奇偶数)
        int flag=0;
      //直到队列queue为空结束
        while(!queue.isEmpty()) {
            List<Integer> temp = new ArrayList<>();  //存储每行的结果
          //每次准备出队的时候+1(每次开始肯定是一行的内容进行循环)
            flag++;
          // 每次出队时候里面存的都是一行的节点
            for (int i=queue.size();i>0;i--) {
                TreeNode t = queue.poll(); //出队
                temp.add(t.val);  //存储出队结果值
                if (t.left != null) {
                    queue.add(t.left); //队列添加左节点
                }
                if (t.right != null) {
                    queue.add(t.right); //队列添加右节点
                }
            }
            //奇数行(第一行flag=1 第三行flag=3)
                if(flag%2==1){
                    res.add(temp); //每行结果添加到res集合
                }
            //偶数行(第二行flag=2 第四行flag=4)
                if(flag%2==0){
                    List<Integer> ou = new ArrayList<>();
                    for(int i=temp.size()-1;i>=0;i--){
                        ou.add(temp.get(i));
                    }
                    res.add(ou); //每行结果添加到res集合
                }

        }
        return res;
    }

}

public class ErChaShu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for (int i = 0; i < n; i++) {
            a[i]=input.nextInt();
        }
        System.out.println(verifyPostorder(a));
    }

    public static boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);  // 调用方法( 数组postorder i j )
    }

    public static boolean recur(int[] postorder, int i, int j) {
        if(i >= j){
            return true;  //子树节点<=1 肯定true
        }
        
     //找左子树
		int chang = i;
        while(postorder[chang] < postorder[j]){  //左边肯定比根节点小(第一个大的数字就是右节点的开始位置)
            chang++;
        }
       
     //找右子树
 		int zhong = chang;  //找到第一个 > postorder[j]的值就是右子树的开始位置   
		while(postorder[chang] > postorder[j]) {  //右边肯定都比根节点大
            chang++;
        }

        //判断长度是否相等  而且左右子树也是二叉搜索树(递归)
            return chang==j&&recur(postorder,i,zhong-1)&&recur(postorder,zhong,j-1); //j位置是左右根的根
    }

}

public class LuJing {
    private ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        TreeNode root=new TreeNode(5); //根节点3
        TreeNode r1=new TreeNode(4);
        root.left=r1;
        TreeNode r2=new TreeNode(8);
        root.right=r2;
        TreeNode r21=new TreeNode(11);
        r2.left=r21;
        TreeNode r22=new TreeNode(13);
        r2.right=r22;
        int sum=input.nextInt();
        //返回list集合先转数组toArray() 然后Arrays.toString()转字符串输出
        System.out.println(pathSum(root,sum));
    }

    private Stack<Integer> path = new Stack<Integer>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null){
            return paths;  //如果空树 返回默认空paths集合
        }
        path.push(root.val);  //存入当前节点值
        target = target -root.val;  //更新剩下的target
        if(target == 0 && root.left == null && root.right == null){  //如果target找到了 而且到最底层(叶子节点)
            paths.add(new ArrayList<Integer>(path)); //path放入paths集合
        }
        FindPath(root.left, target);  //左递归
        FindPath(root.right, target);  //右递归
        path.pop(); //回溯 弹出最后一个点往上返
        return paths; //返回paths集合
    }
    
}

// 定义节点类
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

//具体实现方法
   public static Node copyRandomList(Node head) {
      //创建HashMap集合
        HashMap<Node,Node> map = new HashMap<>();
        Node cur=head; //新建节点指向head
      //复制节点值
        while(cur!=null){
           //存储put:<key,value1>
            map.put(cur,new Node(cur.val)); //顺序遍历
            cur=cur.next;
        }
      //复制节点指向
      cur=head; //上面已经动过了重新指向head
        while(cur!=null){
            //得到get:<key>.value2,3
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
      //返回复制的链表
        return map.get(head);
    }

class Solution {
    Node pre, head;
    public Node treeToDoublyList(Node root) {
    //判断空树 
        if(root == null) return null;
    //中序遍历 左根右(递增)
        dfs(root);
   //处理头尾节点(相互指向)  
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(Node cur) {
      //节点为空  
		if(cur == null) {
			return;
		}
	 //左子树	
        dfs(cur.left);
        if(pre != null){
		 	pre.right = cur;  //不为空 前置节点的右节点指向当前节点
        }else 
			head = cur;  //为空 让头指针定位
        
		cur.left = pre;  //当前节点左边是前置节点
        pre = cur;  //往后移动

	//右子树
        dfs(cur.right);
    }
}

    public ArrayList<String> Permutation(String str) {       
       ArrayList<String> ans=new ArrayList<>();//所有排列的可能都在这
       if(str!=null||str.length()>0){  //str真实存在
           help(0,str.toCharArray(),ans);
           Collections.sort(ans);  //调用方法排序
       }
         return ans;
    }
    
   public static void help(int i,char[] cha,ArrayList<String> ans){
        if(i==cha.length-1){  //找到最后位置
            String val=String.valueOf(cha);  //转字符串
            if(!ans.contains(val)){
                ans.add(val);  //答案里面没有就添加到ans
            }
        }else{
            for(int j=i;j<cha.length;j++){
                 swap(i,j,cha);//依次选一个数固定住
                help(i+1,cha,ans);//让后面的进行全排列
                swap(i,j,cha);//恢复原来的模样，回溯关键

            }
        }
   }    
    
    //两者交换
    public static void swap(int i,int j,char[] cha){
        char temp=cha[i];
        cha[i]=cha[j];
        cha[j]=temp;
    }
           
}

//1.摩尔投票法
public static int majorityElement(int[] nums) {
        int votes=0; //投票和
        int x=0; //众数
        for(int i=0;i<nums.length;i++){
            if(votes==0){
                x=nums[i]; //如果当前位置votes=0 众数换当前值
            }
		//判断当前值是不是众数
            if(nums[i]==x){
                votes++;  //是众数,投票数加一
            }else{
                votes--;  //不是众数,投票数减一
            }
        }
        return x; //返回众数
    }


//2.排序之后取中位数
	public int majorityElement(int[] nums) {
        Arrays.sort(nums);  //对数组排序
        return nums[nums.length/2];  //其他数字只出现一次 所以超过一半的数字肯定是中间位置开始
    }

//3.map集合存储次数 然后找长度超过一半的数组值
	public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length==0){
            return 0;
        }
        int flag=0;
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<array.length;i++){
            int c=array[i];
            map.put(c,map.containsKey(c)?map.get(c)+1:1); 
        }
        for(int i=0;i<array.length;i++){
            int c=array[i];
            if(map.get(c).intValue()>=array.length/2+1){
                flag=c;
            }
        }
        return flag;
    }

//1.排序之后将前k个值赋给新的数组
 public int[] getLeastNumbers(int[] arr, int k) {
        Arrays.sort(arr);
        int[] a=new int[k];
        for(int i=0;i<k;i++){
            a[i]=arr[i];
        }
        return a;
    }

//动态规划
   public static int maxSubArray(int[] nums) {
     //接答案(默认第一个值就是最大的和)
       int res=nums[0];
     //记录每个位置能取得最大值
       int[] dp=new int[nums.length];
           dp[0]=nums[0];  //初始最大值是第一个值
     //依次遍历
       for (int i=1;i<nums.length;i++) { //从第二个位置开始
          if(dp[i-1]>0){  //如果前面的和大于0
              dp[i]=dp[i-1]+nums[i]; //就加上当前值更大
          }else{  //前面的和小于0  那我还不如当前值为和
              dp[i]=nums[i];  //更换为当前值
          }
          res=Math.max(res,dp[i]);  //每次把当前值的dp[i]和最大值比较更新res
       }
       return res; //res最后就是dp数组最大值
   }

//1. 按位拆除判断(超时)
    public static int countDigitOne(int n) {
        int res=1;
        if(n==0){  //0的话出现0次
            res=0;
        }
        if(n==1){  //1的话出现1次
            res=1;
        }
        for(int i=2;i<=n;i++){  //从2开始
            res+=jige(i);
        }
        return res;
    }
    //统计1的次数
    public static int jige(int i){
        int sum=0;
        while(i!=0){  //缩小范围到0
            if(i%10==1){
                sum++;  //出现1的时候计数器+1
            }
            i=i/10; //不断缩小
        }
        return sum;
    }


//2. 数学归纳法
	public int countDigitOne(int n) {
        int res = 0;
        for (long m = 1; m <= n; m *= 10) {
            long a = n / m;
            long b = n % m;
            res += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);
        }
        return res;
    }

public static int findNthDigit(int n) {
       int res=0;
       if(n<10){
           return n;  //前10位是按照顺序0123456789
       }
       int i=1;
       while(n>i*(Math.pow(10,i-1)*9)){  // 9(10个) 99(90个) 999(900个)
           n-=i*Math.pow(10,i-1)*9;
           i++;
       }
       char[] result=String.valueOf((int)Math.pow(10,i-1)+(n-1)/i).toCharArray();//我们用字符串来接收值，方便找位数 result结果为我们要的那个数的
       int value=result[(n-1)%i]-'0';    //(n-1)%位数 得出我们要的第x位的数
       return value;
   }

class Solution {
        public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        Map<Character, Integer> map = new HashMap<>();//key出现的字符，value对应的最新的位置
        // try to extend the range [i, j]
        int start=0;
        for (int end = 0; end < n; end++) {
            if (map.containsKey(s.charAt(end))) {
                start = Math.max(map.get(s.charAt(end)) + 1, start);//由于重复的坐标不知道在start的前方还是后方，所以要取个最大值
            }
            ans = Math.max(ans, end - start + 1);  //更新最大长度
            map.put(s.charAt(end), end);  //存放的字符对应位置更新
        }
        return ans;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        System.out.println(nthUglyNumber(n));  //调用方法
    }

    public static int nthUglyNumber(int n) {
        int p2=0;  //只乘2
        int p3=0;  //只乘3
        int p5=0;  //只乘5
        int[] dp=new int[n]; //存放所有的丑数
        dp[0]=1; //第一个丑数是1
        for(int i=1;i<n;i++){
            dp[i]=Math.min(dp[p2]*2,Math.min(dp[p3]*3,dp[p5]*5));  //从第二位开始求当前位置丑数
		//看是哪个指针走了就跳后面	
            if(dp[i]==dp[p2]*2){  
                p2++;
            }
            if(dp[i]==dp[p3]*3){
                p3++;
            }
            if(dp[i]==dp[p5]*5){
                p5++;
            }
        }
        return dp[n-1];  //最后返回n-1结果
    }
    
}