Compared to the solution itself, the rigorous proof is cumbersome, so this editorial only presents the answer.
Henceforth, we assume the side length of each square is \(1\).

One of the following two tilings shown in the figure below is optimal.

• The left side of the figure: fill a \(k \times k\) region with squares in a grid, allowing gaps only in the rightmost row, packing squares from the top.
• The right side of the figure: fill a \(k \times (k+1)\) region with squares in a grid, allowing gaps only in the rightmost row, packing squares from the top.

For a tiling of the above forms, the number of pairs of tiles sharing exactly one full side can be computed as follows.

• \(2N-\) (perimeter of the region) \(/2\)
  • For the left side of the figure, \(2 \times 7 - (3+3+3+3)/2 = 8\)
  • For the right side of the figure, \(2 \times 10 - (3+4+3+4)/2 = 13\)

Proof:
The total perimeter of all tiles is \(4N\).
Of this, an amount equal to the perimeter of the region is wasted.
The part that is not wasted repeats a structure in which \(2\) units of a tile’s perimeter are consumed to form one pair of tiles sharing exactly one full side.
Writing this as a formula gives \((4N-\) (perimeter of the region) \()/2\), which matches the formula above.

In the end, the following solution holds.

• Find the maximum \(k\) satisfying \(k \times k < N\).
• If \(N \le k \times (k+1)\), then \(k \times (k+1)\) is an optimal arrangement; otherwise, \((k+1) \times (k+1)\) is an optimal arrangement.
• For the arrangement found, solve using the formula above.

The time complexity depends on the part that finds the maximum \(k\) satisfying \(k \times k < N\), which is \(O(\log N)\) even using binary search (the sample implementation uses sqrt).

Incidentally, the resulting sequence of answers also appears in OEIS.

Sample Implementation (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;
}