Description:

Xiaobai and Xiaolan have a math class together. After class, the teacher left an assignment to find the general formula of the following sequence:

A(0)=0 A(1)=1 A(2i)=A(i) (For any i>0) A(2i+1)=A(i)+A(i+1) (For any i>0)

Xiaobai, as a math enthusiast, quickly worked out the general term formula of this sequence. Therefore, Xiaobai tells Xiaolan that he has done it, but in order to prevent Xiaolan from copying homework, Xiaobai does not want to publish the formula. Therefore, in order to prove to Xiaolan that he did make this question to achieve the purpose of showing off, Xiaobai has come up with a wonderful method: let Xiaolan say a positive integer N, and Xiaobai will say the value. If Xiaobai can quickly say the correct answer when N is large, it means that Xiaobai has indeed got the formula. But there is a big loophole in this method: Xiaolan can't do it himself, so he can't verify whether Xiaobai's answer is correct. As a good friend of Xiaolan, can you help Xiaolan?

Input and output format:

Input format:

The first line of the input file has and only one positive integer T, which represents the number of groups of test data.

From line 2 to T+1, each line has a nonnegative integer N.

Output format:

The output file contains a total of T lines.

Line i should contain a number without extra prefix 0, and its value should be equal to (n is the integer read in line i+1 of input data)

## Input and output examples

Input sample ා 1:

3 1 3 10

Output sample 1:

1 2 3

## explain

For 20% of the data, n < = 10 ^ 8

For 50% of the data, n < = 10 ^ 12

For 100% data, T < = 20, n < = 10 ^ 100

import java.math.BigInteger; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class ArrayTest { static BigInteger f(BigInteger n) { BigInteger x_2 = new BigInteger("2"); if (n.equals(BigInteger.ZERO)) { return BigInteger.ZERO; } else if (n.equals(BigInteger.ONE)) { return BigInteger.ONE; } else if (n.mod(x_2).equals(BigInteger.ZERO)) { return f(n.divide(x_2)); } else { //n-1 BigInteger sub1 = n.subtract(BigInteger.ONE); //n+1 BigInteger add1 = n.add(BigInteger.ONE); return f(sub1.divide(x_2)).add(f(add1.divide(x_2))); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); List<BigInteger> list = new ArrayList<>(); int count = 0; while (count < n) { list.add(sc.nextBigInteger()); count += 1; } list.forEach(ele -> System.out.println(f(ele))); } }

Online OJ test platform prompts:

Case situation: total cases: 10 success: 2 failure: 0 exception: 8

At present, I don't know how to improve them. Please help us. Thank you.