Osim's Maze

Welcome to Osim’s maze!

Unfortunately, you are in the maze right now and you want to come outside the maze. But, in order to do that, you have to unlock some locks with keys. So, you are given $Q$ locks each of which is some integer $x_i$. You have an array of $N$ integers: $a_1, a_2, a_3, \dots, a_n$. A key for a lock $x_i$ is some non-empty subset of any positive size $k$ containing $s_1, s_2, \dots, s_k$ of the array such that $x_i \mathbin{\&} (s_1 \mathbin{|} s_2 \mathbin{|} ... \mathbin{|} s_k) == 0$ , where $\mathbin{\&}$ means $bitwise\hspace{1mm}AND$ and $\mathbin{|}$ means $bitwise\hspace{1mm}OR$. But, as you are a problem solver, you wonder how many subsets of your array exist as keys for a lock $x_i$.

This is a companion discussion topic for the original entry at https://toph.co/p/osim-s-maze