Ông Từ đang ôn bài tập về dãy số, hôm nay ông có một bài khá hóc búa. Ông được cho hai dãy số nguyên không âm ~a_1, a_2, ..., a_n~ và ~k_1, k_2, ..., k_n~.

Một dãy con gồm các phần tử ~a_{i_1}, a_{i_2}, ..., a_{i_m}~ được gọi là đẹp nếu nó thoả mãn các điều kiện sau:

~1 ≤ i_1 < i_2 < ... < i_m ≤ n~.

Với mọi chỉ số ~1 < j \le m~ trong dãy con, ta có ~bitCount~ (~a_{i_j}~ ~AND~ ~a_{i_{j-1}}~) = ~k_{i_{j}}~.

Trong đó ~bitCount(x)~ là số lượng bit 1 trong biểu diễn nhị phân của số nguyên ~x~.

Ông Từ muốn tìm độ dài lớn nhất của một dãy con đẹp.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 ≤ n ≤ 10^5)~ — độ dài của hai dãy.

Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~ ~(0 ≤ a_i < 2^{20})~.

Dòng thứ ba chứa ~n~ số nguyên ~k_1, k_2, ..., k_n~ ~(0 \le k_i \le 20)~.

Output

In ra một số nguyên ~m~ — độ dài của dãy con đẹp dài nhất.

Scoring

Subtask 1 (~20%~): ~1 ≤ n ≤ 5000, 0 ≤ a_i < 2^{20}~.

Subtask 2 (~30%~): ~1 ≤ n ≤ 10^4, 0 ≤ a_i < 2^8~.

Subtask 3 (~50%~): ~1 ≤ n ≤ 10^5, 0 ≤ a_i < 2^{20}~.

Input

5
5 3 5 3 5
10 1 20 1 20

Output

2