SP12824 PBBN2 - Print Big Binary Numbers

Some answers for some problems could be huge binary numbers. In order to check the computation, one could ask you the sum of its digits. With a little base, the answer is a small number too, but not with a bigger base. [XerK](http://www.spoj.com/problems/PELLFOUR/) would like to avoid precomputed results and wish check you've computed his huge numbers. Here's a problem that check computation of a big number N. A [tutorial edition](http://www.spoj.com/problems/PBBN1/) exists without language restrictions. Let define the function CHK(N, B): Input : N a big number in binary representation, B a power of two. Consider N as a base B number. Output : the sum of its digits in this base. Example :with B=2^8, 12345678 = 78 + 97\*B + 188\*B\*B, so CHK(12345678, B) = 78 + 97 + 188 This should be easily computed with few bitwise-AND, bitshifts and additions.

The input begins with the number T of test cases in a single line. In each of the next T lines there are four integers A, B, C, D, given in base 10.

For each test case : \* compute N = (A^B) XOR (C^D). \* print CHK(N, 2^16384) as a base 10 number. (^ denote the power, and XOR the bitwise operator)