CF809C Find a car

After a wonderful evening in the restaurant the time to go home came. Leha as a true gentlemen suggested Noora to give her a lift. Certainly the girl agreed with pleasure. Suddenly one problem appeared: Leha cannot find his car on a huge parking near the restaurant. So he decided to turn to the watchman for help. Formally the parking can be represented as a matrix $ 10^{9}×10^{9} $ . There is exactly one car in every cell of the matrix. All cars have their own machine numbers represented as a positive integer. Let's index the columns of the matrix by integers from $ 1 $ to $ 10^{9} $ from left to right and the rows by integers from $ 1 $ to $ 10^{9} $ from top to bottom. By coincidence it turned out, that for every cell $ (x,y) $ the number of the car, which stands in this cell, is equal to the minimum positive integer, which can't be found in the cells $ (i,y) $ and $ (x,j) $ , $ 1

The first line contains one integer $ q $ $ (1

Print exactly $ q $ lines — in the first line print the answer to the first request, in the second — the answer to the second request and so on.

Let's analyze all the requests. In each case the requested submatrix is highlighted in blue. In the first request $ (k=1) $ Leha asks only about the upper left parking cell. In this cell the car's number is $ 1 $ . Consequentally the answer is $ 1 $ .  In the second request $ (k=5) $ suitable numbers are $ 4,1,2,3,2,1 $ . Consequentally the answer is $ 4+1+2+3+2+1=13 $ .  In the third request $ (k=10000) $ Leha asks about the upper left frament $ 5×5 $ of the parking. Since $ k $ is big enough, the answer is equal to $ 93 $ .  In the last request $ (k=2) $ none of the cur's numbers are suitable, so the answer is $ 0 $ .