E. Do You Love Your Hero and His Two-Hit Multi-Target Attacks?
binary search; brute force; constructive algorithms; dp; geometry; greedy; math
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.