A. AND-OR closure
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a set $$$A$$$ of $$$n$$$ non-negative integers, we define its AND-OR closure as the $$$B$$$ with smallest size such that:

  • $$$A\subseteq B$$$
  • If $$$x,y\in B$$$, then $$$(x\texttt{ AND }y)\in B$$$
  • If $$$x,y\in B$$$, then $$$(x\texttt{ OR }y)\in B$$$

Find the size of the AND-OR closure of $$$A$$$.

Here AND denotes the bitwise AND operation, and OR denotes the bitwise OR operation.

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)  — the size of the set $$$A$$$.

The second line contains $$$n$$$ distinct integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$ , $$$a_n$$$ ($$$0\leq a_i \lt 2^{40}$$$)  — which represent the elements of $$$A$$$.

Output

Print the size of the AND-OR closure of $$$A$$$.

Examples
Input
4
0 1 3 5
Output
5
Input
5
0 1 2 3 4
Output
8
Note

In the first sample, the AND-OR closure of $$$A$$$ is $$$\{0, 1, 3, 5, 7\}$$$.

In the second sample, the AND-OR closure of $$$A$$$ is $$$\{0, 1, 2, 3, 4, 5, 6, 7\}$$$.