题目描述

小 F 和小 W 在玩游戏，一共有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 个石头。

小 W 先手，小 F 后手，两个人轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

趁着小 W 不注意，小 F 想搞一点暗箱操作，从每堆石子里都偷偷拿出 $k$ 个石子，然后再开始游戏。她可以不拿，但是不能把任何一堆石子偷偷拿光。

求有多少种可能的 $k$ 使得拿完后小 F 必胜。

输入格式

第一行一个整数 $n$ 。

第二行 $n$ 个整数表示 $a_i$ 。

输出格式

输出一个整数表示答案。

样例

4
4 6 8 10

2

数据范围与约定

对于 $30\%$ 的数据， $n\leq 10000,a_i\leq 1000$ 。

对于 $60\%$ 的数据， $n\leq 10000,a_i\leq 10^6$ 。

对于 $100\%$ 的数据， $n\leq 200000,a_i\leq 10^{18}$ 。