**Tea with Tangerines solution codeforces** – There are 𝑛n pieces of tangerine peel, the 𝑖i-th of them has size 𝑎𝑖ai. In one step it is possible to divide one piece of size 𝑥x into two pieces of positive integer sizes 𝑦y and 𝑧z so that 𝑦+𝑧=𝑥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?

Table of Contents

## [Solution] Tea with Tangerines solution codeforces

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

The first line of each test case contains the integer 𝑛n (1≤𝑛≤1001≤n≤100).

Then one line follows, containing 𝑛n integers 𝑎1≤𝑎2≤…≤𝑎𝑛a1≤a2≤…≤an (1≤𝑎𝑖≤1071≤ai≤107).

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

## [Solution] Tea with Tangerines solution codeforces

input

output

10 0 4

## [Solution] Tea with Tangerines solution codeforces

In the first test case, we initially have a piece of size 11, so all final pieces must have size 11. The total number of steps is: 0+1+2+3+4=100+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 00 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 10001000, and it is less than 22 times bigger than the minimum piece of size 550550. 44 steps are done. We can show that it is the minimum possible number of steps.