시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 2 | 1 | 1 | 50.000% |
Track designer Ger Kilke is going to create a new track for Formula-Y race. Ger is planning to use his favorite way to design the track. He introduced the Cartesian coordinates at the plane where the track will be built, X axis goes from left to right, Y axis goes from bottom to top. The track must satisfy the following conditions:
Ger would like to make a track of n segments such that it had exactly k intersections. Mathematicians have told him that it is possible only if 0 ≤ k ≤ n2(n2 - 1) / 2, where n2 is equal to n / 2 rounded down. So Ger has chosen the value of k that satisfies this condition. Help Ger to design the track.
Input data contains multiple test cases. The first line contains t — the number of tests.
Each of the following t lines contains two positive inegers: n and k (1 ≤ n ≤ 1000, 0 ≤ k ≤ n2(n2 - 1) / 2, where n2 is equal to n / 2 rounded down) — the number of segments of the track and the number of desired intersections.
The sum of values of n in one input data doesn't exceed 104.
Print the track description for each of t tests.
Each description must contain n + 1 lines, the i-th of these lines must contain coordinates of the i-th vertex of the polyline. List vertices from the start to the finish. Coordinates must be positive integers not exceeding 3000.
It is guaranteed that such polyline always exists for the given constraints.
2 4 1 3 0
1 3 3 3 3 1 2 1 2 5 3 9 3 1 1 1 1 4