考虑一棵叶子节点被赋予整数权值的二叉树。如果对于每一个非叶子节点，其左子树中所有叶子节点的权值之和等于其右子树中所有叶子节点的权值之和，则称这样的树为平衡树。例如，下图中的树就是一棵平衡树。

图 I.1. 一棵平衡树

如果一棵平衡树的所有叶子节点的权值从左到右排列构成的序列是序列 $A$ 的一个子序列，则称该平衡树隐藏在序列 $A$ 中。这里，子序列是指通过删除原序列中零个或多个元素且不改变剩余元素顺序而得到的序列。

例如，上图中的平衡树隐藏在序列 3 4 1 3 1 2 4 4 6 中，因为 4 1 1 2 4 4 是它的一个子序列。

现在，你的任务是在给定的整数序列中，找到隐藏在其中的叶子节点数量最多的平衡树。事实上，上图中所示的树就是隐藏在上述序列中的叶子节点数量最多的平衡树。

输入格式

输入包含多组数据。每组数据表示一个整数序列 $A$，格式如下：

$N$ $A_1 \ A_2 \ \dots \ A_N$

其中 $1 \le N \le 1000$ 且 $1 \le A_i \le 500$（对于 $1 \le i \le N$）。$N$ 是输入序列的长度，$A_i$ 是序列的第 $i$ 个元素。

输入以一行只包含一个 0 的数据结束。数据集的数量不超过 50。

输出格式

对于每组数据，找到隐藏在 $A$ 中的叶子节点数量最多的平衡树，并输出其叶子节点的数量。

样例

输入 1

9
3 4 1 3 1 2 4 4 6
4
3 12 6 3
10
10 9 8 7 6 5 4 3 2 1
11
10 9 8 7 6 5 4 3 2 1 1
8
1 1 1 1 1 1 1 1
0

输出 1

6
2
1
5
8