Solution to Chef and Squares challenge, timing out in Java but not in C++

I was solving a problem on codechef (online judge and contest organizer). I was writing my code in Java and was getting TLE at last testcase where as I wrote the same code in C++ and it was accepted. Now I know C++ is faster then java but If anyone could help me optimize my Java code ?

Here is the question


Chef has finished his freshman year in college. As a present, his
parents gave him a new problem to solve: Chef has to fill a K x K
square grid of integers in a certain way. Let us say that such a grid
is valid if:

• Each cell contains an integer from 1 and K (inclusive).

• No integer appears twice in the same row or the same column.

Let F(K) be maximum possible distance between the center of the square and the closest
cell that contains 1, among all possible squares with the side length
K.


Here, we use the following notions:

• The distance between cell (x, y) and (i, j) is equal to |x-i|+|y-j|.

• The center of a K × K square is cell ((K+1)/2, (K+1)/2) for odd K.

Input


The first line of input contains a single integer T denoting the
number of test cases. Each test case consists of a single line
containing a single odd integer K.

Output


For each test case, print K lines each consisting of K space separated
integers giving some square grid where the distance from the center of
the grid to the nearest 1 is exactly F(K). If there's more than 1
possible answer output any of them.

Constraints


Ki is odd.

Subtask #1 (10 points):


1 ≤ T ≤ 50

1 ≤ Ki ≤ 5

Subtask #1 (90 points):


1 ≤ T ≤ 10

1 ≤ Ki < 400

Example


Input:

2
1
3

Output:

1
3 2 1
1 3 2
2 1 3

Here is my code in Java

```
import java.util.*;
import java.io.*;

public class Main {
public static void main(String[] args) throws IOException{
BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parse

My first observation was the same as @EmilyL.'s: that you're performing unneeded string concatenations. Upon investigation, however, it turned out to be a loser to substitute two invocations of System.out.print() methods for a string concatenation plus one method invocation -- the result ran about 70% slower than the original code for me.

It took a while for the lightbulb to turn on, but that slowdown is a key symptom of the underlying problem: System.out is unbuffered, at least when it's not connected to a terminal. In a comment you described addressing the problem by building the output in a StringBuilder and then printing it all at once. That's a viable mechanism for buffering manually, but cleaner and easier to integrate into your original solution would have been to wrap a buffered stream around System.out and print to that. In other words, at the top of main() add ...

PrintStream out = new PrintStream(new BufferedOutputStream(System.out));

... and everywhere else print to out instead of to System.out(). Doing that cut my run time by more than 50% relative to the original code, for a maximal-size test set.

StackExchange Code Review Q#146513, answer score: 9