解法に対して 厳密な証明 は煩雑なので、この解説では答えのみを示します。
また、以降は正方形の一辺の長さは \(1\) であるとして説明します。

下図の \(2\) 通りの敷き詰めのいずれかが最善です。

• 図の左側、 \(k \times k\) の領域に正方形をグリッド状に敷き詰める。ただし、右端の行のみ空きを許し、上から正方形を詰めていく。
• 図の右側、 \(k \times (k+1)\) の領域に正方形をグリッド状に敷き詰める。ただし、右端の行のみ空きを許し、上から正方形を詰めていく。

上記の形の敷き詰めについて、一辺を完全に共有しているタイルのペアの個数は以下のように求められます。

• \(2N-\) (領域の周長) \(/2\)
  • 図の左側の場合、 \(2 \times 7 - (3+3+3+3)/2 = 8\)
  • 図の右側の場合、 \(2 \times 10 - (3+4+3+4)/2 = 13\)

証明:
全てのタイルの周長の合計は \(4N\) です。
このうち領域の周長と同じ長さぶんだけが空費されます。
空費されないぶんは、タイルの周長 \(2\) を消費して \(1\) 組の一辺を完全に共有しているタイルのペアを作るという構造が繰り返されます。
これを式に起こすと、 \((4N-\) (領域の周長) \()/2\) となり、上記の公式に一致します。

結局、以下の解法が成り立ちます。

• \(k \times k < N\) を満たす最大の \(k\) を求める。
• \(N \le k \times (k+1)\) なら \(k \times (k+1)\) が最適な配置、そうでなければ \((k+1) \times (k+1)\) が最適な配置である。
• 求めた配置について、上記の公式を使って求解する。

計算量は \(k \times k < N\) を満たす最大の \(k\) を求める部分に依存しますが、二分探索を使っても \(O(\log N)\) です (実装例では sqrt を活用しています)。

ちなみに、答えとなる数列は OEIS にも存在します。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t--){
    ll n;
    cin >> n;
    ll k=sqrt(n);
    while(k*k<n){k++;}
    while(k*k>=n){k--;}
    if(n<=k*(k+1)){
      cout << 2*n-(k+k+1) << "\n";
    }
    else{
      cout << 2*n-2*(k+1) << "\n";
    }
  }
  return 0;
}