Karthikeya Numbers

A number $N$ is said to be $X$-valid if $N$ is even, and all numbers from $\{1, 2, ..., N\}$ can be split into $\frac{N}{2}$ mutually exclusive pairs of $2$, where each pair has a sum which is a power of $X$. Given $N$ and $X$, find the number of integers $i$ satisfying $1 \le i \le N$ and $i$ is $X$-valid. ### Input - The first line of input will contain a single integer $T$, denoting the numb