Deep beneath the surface of a forgotten sea lies the Silent Abyss — a realm where numbers do not merely exist, but live.

Every integer in the Abyss is embodied as an Aqua Jelly a luminous creature woven from binary sparks. Each spark is either active or dormant, and together they encode the jelly's identity.

When two jellies meet in the deep current, something remarkable happens. Every spark that is active in exactly one of them begins to oscillate — flickering restlessly, searching for a partner. Sparks active in both jellies, or dormant in both, remain perfectly calm. The scholars of the Abyss called the count of oscillating sparks the resonance of the pair.

Through centuries of study, the scholars uncovered a sacred law of inheritance. Jelly $$$y$$$ earns the right to be called an heir of jelly $$$x$$$ if and only if their resonance is a prime number — for prime counts represent patterns that are indivisible and eternally stable in the ocean currents.

Formally, for two non-negative integers $$$x$$$ and $$$y$$$, define their resonance as $$$$$${R}(x, y) = \operatorname{popcount}(x \mathbin{|} y) - \operatorname{popcount}(x \mathbin{\&} y)$$$$$$

where $$$\operatorname{popcount}(v)$$$ denotes the number of set bits in the binary representation of $$$v$$$, the operation $$$|$$$ denotes bitwise OR, and the operation $$$\&$$$ denotes bitwise AND.

Jelly $$$y$$$ is an heir of jelly $$$x$$$ if and only if $$${R}(x, y)$$$ is prime.

You are an explorer who has descended into the Abyss with $$$q$$$ questions. Each question names an ancestor jelly $$$x$$$ and a depth $$$n$$$. count how many jellies $$$y$$$ in the range $$$[1, n]$$$ are heirs of $$$x$$$.