[Solution] Patchouli's Magical Talisman Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Patchouli's Magical Talisman Codeforces Solution | Codeforces Problem Solution 2022

B. Patchouli's Magical Talisman

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Patchouli is making a magical talisman. She initially has n$n$ magical tokens. Their magical power can be represented with positive integers a1,a2,…,an$a_1,a_2,\dots ,a_n$.

Patchouli may perform the following two operations on the tokens.

Solution Click Below:-  CLICK HERE

• Fusion: Patchouli chooses two tokens, removes them, and creates a new token with magical power equal to the sum of the two chosen tokens.
• Reduction: Patchouli chooses a token with an even value of magical power x$x$, removes it and creates a new token with magical power equal to x2$\frac{x}{2}$.

Tokens are more effective when their magical powers are odd values. Please help Patchouli to find the minimum number of operations she needs to make magical powers of all tokens odd values.

Input

Each test contains multiple test cases.

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

Cirno's Perfect Bitmasks Classroom Codeforces Solution

Patchouli's Magical Talisman Codeforces Solution

Manipulating History Codeforces Solution

The Enchanted Forest Codeforces Solution

Railway System Codeforces Solution

Sanae and Giant Robot Codeforces Solution

For each test case, the first line contains one integer n$n$ (1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$) — the initial number of tokens.

The second line contains n$n$ intergers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤109$1\le a_i\le {10}^9$) — the initial magical power of the n$n$ tokens.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, print a single integer — the minimum number of operations Patchouli needs to make all tokens have an odd value of magical power.

It can be shown that under such restrictions the required sequence of operations exists.