У Поликарпа есть последовательность, состоящая из n целых неотрицательных чисел: a1, a2, ..., an.
Определим функцию f(l, r) (l, r — целые, 1 ≤ l ≤ r ≤ n) для последовательности a как операцию побитового ИЛИ всех элементов последовательности с индексами от l до r. Формально: f(l, r) = al | al + 1 | ... | ar.
Поликарп выписал на листок бумаги значения функции f(l, r) для всех l, r (l, r — целые, 1 ≤ l ≤ r ≤ n). Теперь он хочет узнать, сколько различных чисел у него получилось.
Помогите Поликарпу, посчитайте количество различных значений функции f(l, r) для заданной последовательности a.
Выражение x | y обозначает применение операции побитового ИЛИ к числам x и y. Данная операция есть во всех современных языках программирования, например, в языке C++ и Java она обозначается «|», в Pascal — «or».
Выходные данные
Выведите единственное целое число — количество различных значений функции f(l, r) для заданной последовательности a.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом тестовом примере на листочке Поликарпа будет записано 6 чисел: f(1, 1) = 1, f(1, 2) = 3, f(1, 3) = 3, f(2, 2) = 2, f(2, 3) = 2, f(3, 3) = 0. Среди этих чисел ровно 4 различных числа: 0, 1, 2, 3.