[Solution] Tea with Tangerines Codeforces Solution

B. Tea with Tangerines

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

There are n$n$ pieces of tangerine peel, the i$i$-th of them has size ai$a_i$. In one step it is possible to divide one piece of size x$x$ into two pieces of positive integer sizes y$y$ and z$z$ so that y+z=x$y+z=x$.

You want that for each pair of pieces, their sizes differ strictly less than twice. What is the minimum possible number of steps needed to satisfy the condition?

Input

The first line of the input contains a single integer t$t$ (1≤t≤100$1\le t\le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains the integer n$n$ (1≤n≤100$1\le n\le 100$).

Then one line follows, containing n$n$ integers a1≤a2≤…≤an$a_1\le a_2\le \dots \le a_n$ (1≤ai≤107$1\le a_i\le {10}^7$).

Output

For each test case, output a single line containing the minimum number of steps.

Note

In the first test case, we initially have a piece of size 1$1$, so all final pieces must have size 1$1$. The total number of steps is: 0+1+2+3+4=10$0+1+2+3+4=10$.

In the second test case, we have just one piece, so we don't need to do anything, and the answer is 0$0$ steps.

In the third test case, one of the possible cut options is: 600, 900, (600|700), (1000|1000), (1000|1000|550)$600,900,(600|700),(1000|1000),(1000|1000|550)$. You can see this option in the picture below. The maximum piece has size 1000$1000$, and it is less than 2$2$ times bigger than the minimum piece of size 550$550$. 4$4$ steps are done. We can show that it is the minimum possible number of steps