题目描述

小 T 到 CZ 中学上的第一堂课是物理课，第一堂课 L 老师就把大家带到创新实验室去做实验了，实验的内容是天平称物。众所周知天平是物理实验室中的一种衡量物体质量的仪器，它依据杠杆原理制成，在杠杆的两端各有一个小盘，一端放砝码，另一端放要称的物体，杠杆中央装有指针，两端平衡时，意味着两端的质量相等。

这些道理对学过初中物理的人来说已经是老生常谈了，小 T 原以为这次实验跟初二做过的不会有太大区别，但当他一走进创新实验室，就立即被眼前堆得跟小山一样的砝码震住了，小 T 走上前去拿出几个砝码看了一下，发现所有砝码上标明的质量均为 $2$ 的幂次：$1\text{g},2\text{g},4\text{g},8\text{g},16\text{g},32\text{g}$ 等等，这下小 T 彻底被雷到了，心想这是物理实验室吗？怎么跟计算机中的二进制表示那么相似呢？

正当小 T 想得出神，L 老师已经在大声催促同学们座到指定位置上去做实验了，小 T 和同桌小 S 两人一组很快就把桌上几个物体的质量用天平称出来了，抬头一看周围的同学还都在忙碌着，小 T 就对小 S 说："我们来做个游戏好不好？"小 S 说："做什么游戏？"小 T 说："很简单，我随意抓一把些砝码放到天平的左端，你要在天平的右端放置最少数量的砝码使得天平平衡。"小 S 说："没问题，那我们就开始吧！"游戏开始后，小 S 发现当小 T 放上去的砝码个数较多且相同质量的砝码有多个时有点难办，于是他就找到了会编程的你，希望你帮他处理这个问题。

输入格式

输入数据共有两行，第一行包含一个正整数 $N$，表示小 T 一共抓了 $N$ 个砝码放到了天平的左端。

第二行有 $N$ 个用空格隔开的正整数表示每个砝码的质量，每个砝码的质量都是 $2$ 的幂次，即等于若干个 $2$ 连乘的积，如 $8$ 等于 $3$ 个 $2$ 连乘的积，$64$ 等于 $6$ 个 $2$ 连乘的积，$1024$ 等于 $10$ 个 $2$ 连乘的积等等，特别地我们规定 $1$ 也是 $2$ 的幂次。

输出格式

输出数据仅有一行包含一个正整数表示小 S 最少要在天平的右端放置几个砝码，CZ 中学的物理创新实验室里只有质量为 $2$ 的幂次的砝码，并且每种砝码都取之不尽用之不竭。

样例

2
8 8

1

6
1 1 1 4 1 1

2

提示

样例解释

样例 1 中小 T 抓了两个 $8\text{g}$ 的砝码放到了天平的左端，小 S 只要将一个 $16\text{g}$ 的砝码放到天平的右端就行了，答案为 $1$。

样例 2 中小 T 抓了 $5$ 个 $1\text{g}$ 的砝码和 $1$ 个 $4\text{g}$ 的砝码放到了天平的左端，小 S 只要将一个 $8\text{g}$ 的砝码和一个 $1\text{g}$ 的砝码放到天平的右端就行了，答案为 $2$。

数据范围

$30\%$ 的数据：$N\le 10$，天平左端的 $N$ 个砝码的总质量不超过 $100\text{g}$

$60\%$ 的数据：$N\le 100$，天平左端的 $N$ 个砝码的总质量不超过 $10000\text{g}$

$100\%$ 的数据：$N\le 10000$，天平左端的 $N$ 个砝码的总质量不超过 $2\times 10^9\text{g}$

来源

市赛