ladybugs

Problem Description

Jianzhi was walking around in a garden one day, when he found a line of N ladybugs, each with a mysterious integer written onto it (what?). The ith ladybug from the front has the integer A_i. Through the use of his high-level experimental techniques, he managed to deduce that two ladybugs can only communicate with one another if the integers they carry have a bitwise AND of 0.

He notices that if he randomly removes one ladybug from the line, the two ladybugs in front and behind it will come together and make the line complete again. Jianzhi would like to remove some ladybugs, such that any two adjacent ladybugs are able to communicate with one another, and he also wants to leave the maximum possible number of ladybugs in the line. Help Jianzhi find out what is the maximum number of ladybugs he can leave in the line.

Limits

Subtask 1 (26%): 1 ≤ N ≤ 20, 0 ≤ A_i ≤ 10⁹.

Subtask 2 (22%): 1 ≤ N ≤ 2000, 0 ≤ A_i ≤ 10⁹. All A_i will be equal.

Subtask 3 (52%): 1 ≤ N ≤ 2000, 0 ≤ A_i ≤ 10⁹.

Subtask 4 (0%): Sample Testcases

Input

The first line of input will contain one integer, N.

The second line of input will contain N integers, representing the array A.

Output

The output should contain exactly one integer, the maximum number of ladybugs Jianzhi can leave in the line.

Sample Testcase 1

Input

5
2 1 3 4 6

Output

3

Explanation

Jianzhi can leave the line [2, 1, 4].

Sample Testcase 2

Input

7
2 4 3 2 0 3 4

Output

6

Explanation

Jianzhi can leave the line [2, 4, 2, 0, 3, 4].