CF2072E Do You Love Your Hero and His Two-Hit Multi-Target Attacks?

Akito decided to study a new powerful spell. Since it possesses immeasurable strength, it certainly requires a lot of space and careful preparation. For this, Akito went out into the field. Let's represent the field as a Cartesian coordinate system. For the spell, Akito needs to place $ 0 \le n \le 500 $ staffs at distinct integer coordinates in the field such that there will be exactly $ k $ pairs $ (i, j) $ such that $ 1 \le i < j \le n $ and $ \rho(i, j) = d(i, j) $ . Here, for two points with integer coordinates $ a = (x_a, y_a) $ and $ b = (x_b, y_b) $ , $ \rho(a, b) = \sqrt{(x_a - x_b)^2 + (y_a - y_b)^2} $ and $ d(a, b) = |x_a - x_b| + |y_a - y_b| $ .

The first line of input contains a single number $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. In the only line of each test case, there is a single number $ k $ ( $ 0 \le k \le 10^5 $ ) — the number of pairs of staffs for which the equality $ \rho(i, j) = d(i, j) $ must hold.

For each test case, the first line of output should print the number $ n $ ( $ 0 \le n \le 500 $ ) — the number of placed staffs. In the following $ n $ lines, pairs of integers $ x_i, y_i $ $ (-10^9 \le x_i, y_i \le 10^9) $ should be printed — the coordinates of the $ i $ -th staff. The points in which staffs stand must be distinct.