ACM-ICPC 2017 Asia Nanning F. The Chosen One

地址

Welcome to the 2017 ACM-ICPC Asia Nanning Regional Contest.

Here is a breaking news. Now you have a chance to meet alone with the Asia Director through a game.

All boys and girls who chase their dreams have to stand in a line. They are given the numbers in the order in which they stand starting from 1.

The host then removes all boys and girls that are standing at an odd position with several rounds.

For example if there are n = 8 boys and girls in total. Initially standing people have numbers 1 , 2, 3, 4, 5, 6, 7 and 8. After the first round, people left are 2, 4, 6 and 8. After the second round, only two people, 4 and 8, are still there.

The one who stays until the end is the chosen one.

I know you want to become the chosen one to meet alone with your idol. Given the number of boys and girls in total, can you find the best place to stand in the line so that you would become the chosen one?

Input

First line of the input contains the number of test cases t (1 ≤ t ≤ 1000).

Each of the next t lines contains the integer n which is the number of boys and girls in total, where 2 ≤ n ≤ 10^50.

Output

The output displays t lines, each containing a single integer which is the place where you would stand to win the chance.

样例输入

4
5
12
23
35

样例输出

4
8
16
32

题目大意

给你一个数字k，从1到k每次删去奇数位上的数字，问最后剩下的那个数字是几。

思路

题目很简单，打个表就能发现答案是1,2,2,4,4,4,4,8,8,8,8,8,8,8,8,16…

发现与2的幂有关系。但是n的范围是10^50，太大了，要用大数。写这篇博客就是提醒一下自己要学java大数和C++大数。

代码

import java.math.BigInteger;
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while(t!=0){
            BigInteger n = in.nextBigInteger();
            BigInteger ans = new BigInteger("2");
            while(ans.compareTo(n)<=0) {
                ans = ans.multiply(new BigInteger("2"));
            }
            System.out.println(ans.divide(new BigInteger("2")));
            t--;
        }
        in.close();
    }
}