Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

No tag edit access

A. Powered Addition

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou have an array $$$a$$$ of length $$$n$$$. For every positive integer $$$x$$$ you are going to perform the following operation during the $$$x$$$-th second:

- Select some distinct indices $$$i_{1}, i_{2}, \ldots, i_{k}$$$ which are between $$$1$$$ and $$$n$$$ inclusive, and add $$$2^{x-1}$$$ to each corresponding position of $$$a$$$. Formally, $$$a_{i_{j}} := a_{i_{j}} + 2^{x-1}$$$ for $$$j = 1, 2, \ldots, k$$$. Note that you are allowed to not select any indices at all.

You have to make $$$a$$$ nondecreasing as fast as possible. Find the smallest number $$$T$$$ such that you can make the array nondecreasing after at most $$$T$$$ seconds.

Array $$$a$$$ is nondecreasing if and only if $$$a_{1} \le a_{2} \le \ldots \le a_{n}$$$.

You have to answer $$$t$$$ independent test cases.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases.

The first line of each test case contains single integer $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — the length of array $$$a$$$. It is guaranteed that the sum of values of $$$n$$$ over all test cases in the input does not exceed $$$10^{5}$$$.

The second line of each test case contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$-10^{9} \le a_{i} \le 10^{9}$$$).

Output

For each test case, print the minimum number of seconds in which you can make $$$a$$$ nondecreasing.

Example

Input

3 4 1 7 6 5 5 1 2 3 4 5 2 0 -4

Output

2 0 3

Note

In the first test case, if you select indices $$$3, 4$$$ at the $$$1$$$-st second and $$$4$$$ at the $$$2$$$-nd second, then $$$a$$$ will become $$$[1, 7, 7, 8]$$$. There are some other possible ways to make $$$a$$$ nondecreasing in $$$2$$$ seconds, but you can't do it faster.

In the second test case, $$$a$$$ is already nondecreasing, so answer is $$$0$$$.

In the third test case, if you do nothing at first $$$2$$$ seconds and select index $$$2$$$ at the $$$3$$$-rd second, $$$a$$$ will become $$$[0, 0]$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/11/2020 03:24:28 (i3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|