Constructing every pair of two square numbers with fixed sum

Question

Let $s\in\mathbb{N}$ have the prime factorization $s=2^gp_1^{f_1}p_2^{f_2}\dots q_1^{h_1}q_2^{h_2}\dots$, where $p_i \equiv 1$ and $q_i \equiv 3$ (mod 4). I already know how many distinct $(a,b)\in\mathbb{N}^2$ with $a^2+b^2=s$ exist: If every $h_i$ is even, then there are $(f_1+1)(f_2+1)\dots$, but if one $h_i$ is odd, then there are 0. How do I construct every $(a,b)$, however?