AND-OR closure#12933

AND-OR closure

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

Find the size of the AND-OR closure of .

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 (1 \leq n \leq 2 \cdot 10^5)  — the size of the set .

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

Output

Print the size of the AND-OR closure of .

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

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

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