t = int(input())
for tt in range(t):
    n = int(input())
    ans = [2 * i + 1 for i in range(n)]
    print(*ans)

#include <bits/stdc++.h>

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(a) (int)(a.size())


#ifdef LOCAL
#define __lg(n) log2(n)
#endif

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

template<typename T>
using PQ = priority_queue<T, vector<T>, greater<>>;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int mx = 0;
    for (int i = 0; i < n &mdash; 1; ++i) {
        mx = max(mx, a[i] &mdash; a[i + 1]);
    }
    for (int i = 1; i < n; ++i) {
        if (a[i] < a[i &mdash; 1]) {
            a[i] += mx;
        }
    }
    if (is_sorted(all(a))) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    cin >> t;
    while (t--) solve();
}

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    cnt1 = dict()
    cnt2 = dict()
    x = a[0]
    a = a[1:]
    s = set()
    c = 0
    while x not in s:
        if x not in cnt1:
            cnt1[x] = 0
            cnt2[x] = 0
        cnt1[x] += 1
        cnt2[x] += c
        s.add(x)
        if x & 1:
            x += 1
        else:
            x >>= 1
        c += 1
    for x in a:
        s = set()
        c = 0
        while x not in s:
            if x in cnt1:
                cnt1[x] += 1
                cnt2[x] += c
            s.add(x)
            if x & 1:
                x += 1
            else:
                x >>= 1
            c += 1
    ans = 10 ** 18
    for k, v in cnt1.items():
        if v == n:
            ans = min(ans, cnt2[k])
    print(ans)

#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T,n; string s; ll a[N],c[N],b[N],d[N];
void los(){
    cin >> n >> s,s = " " + s; d[0] = 1;
    for(int i = 1;i <= n;i ++) cin >> a[i],d[i] = 0;
    for(int i = 1;i <= n;i ++) cin >> c[i];
    c[0] = -1e18,b[0] = 0;
    for(int i = 1;i <= n;i ++){
        if(c[i] != c[i &mdash; 1]){
            if(c[i] < c[i-1]) return cout << "No\n",void();
            b[i] = c[i],d[i] = 1;
            for(int j = i;j >= 0;j --){
                if(s[j] == '1'){
                    if(d[j &mdash; 1] && b[j &mdash; 1] + a[j] != b[j]) return cout << "No\n",void();
                    d[j &mdash; 1] = 1,b[j &mdash; 1] = b[j] &mdash; a[j];
                }else break;
            }
        }
    }for(int i = 1;i <= n;i ++){
        if(s[i] == '1') b[i] = b[i-1] + a[i],d[i] = 1;
        if(!d[i]) b[i] = -1e16;
        a[i] = b[i] &mdash; b[i-1];
        if(max(c[i-1],b[i]) != c[i]) return cout << "No\n",void();
    }
    cout << "Yes\n";
    for(int i = 1;i <= n;i ++){
        cout << a[i] << " \n"[i == n];
    }
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}

#include <bits/stdc++.h>
 
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(a) (int)(a.size())
 
using namespace std;
 
using ll = long long;
using ld = long double;
 
const int N = 2228;
 
vector<int> G[N];
int tin[N], tout[N];
int timer = 0;
int cntup[N][N];
int cntdown[N][N];
ll ans1 = 0, ans2 = 0, ans3 = 0;
 
void solve_path(int n, int v, int d) {
    vector<int> dist(n);
    auto dfs = [&](auto &self, int v, int p, int h = 0) -> void {
        dist[v] = h;
        for (int i : G[v]) {
            if (i != p) self(self, i, v, h + 1);
        }
    };
 
    dfs(dfs, v, -1, 0);
 
    for (int i = v + 1; i < n; ++i) {
        if (dist[i] == d) {
            ans1 += d - 1;
        }
    }
}
 
void dfs_tin(int v, int p) {
    tin[v] = timer++;
 
    for (int i : G[v]) {
        if (i != p) dfs_tin(i, v);
    }
    tout[v] = timer;
}
 
void solve() {
    int n, d;
    cin >> n >> d;
    --d;
    for (int i = 0; i < n; ++i) G[i].clear();
    ans1 = 0, ans2 = 0, ans3 = 0, timer = 0;
 
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        G[a - 1].push_back(b - 1);
        G[b - 1].push_back(a - 1);
    }
 
    for (int i = 0; i < n; ++i) solve_path(n, i, d);
    for (int i = 0; i < n; ++i) {
        fill(cntup[i], cntup[i] + N, 0);
        fill(cntdown[i], cntdown[i] + N, 0);
    }
    dfs_tin(0, -1);
 
    for (int i = 0; i < n; ++i) {
        auto dfs = [&](auto &self, int v, int p, int h) -> void {
            if (tin[i] <= tin[v] && tin[v] < tout[i]) ++cntdown[i][h];
            else ++cntup[i][h];
 
            for (int j : G[v]) {
                if (j != p) self(self, j, v, h + 1);
            }
        };
 
        dfs(dfs, i, -1, 0);
    }
 
    vector<int> h(n);
    auto dfs = [&](auto &self, int v, int p, int hh = 0) -> vector<int> {
        int m = len(G[v]);
        vector<vector<int>> who(m);
        vector<int> all;
        all.push_back(v);
        h[v] = hh;
 
        for (int i = 0; i < len(G[v]); ++i) {
            if (G[v][i] == p) continue;
 
            who[i] = self(self, G[v][i], v, hh + 1);
            for (int j : who[i]) all.push_back(j);
 
            for (int j = 0; j < i; ++j) {
                for (int v1 : who[i]) {
                    for (int v2 : who[j]) {
 
                        int D = h[v1] + h[v2] - 2 * hh;
                        if (D >= d) continue;
                        int need = d - D;
                        ans2 += cntup[v][need];
                        int cnt3 = cntdown[v][need];
                        cnt3 -= cntdown[G[v][i]][need - 1];
                        cnt3 -= cntdown[G[v][j]][need - 1];
                        ans3 += cnt3;
 
                    }
                }
            }
        }
 
        return all;
    };
 
    dfs(dfs, 0, -1, 0);
    cout << ans1 + ans2 + ans3 / 3 << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t = 1;
    cin >> t;
    while (t--) solve();
}

#include <bits/stdc++.h>
 
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
 
const char nl = '\n';
typedef long long ll;
typedef long double ld;
 
using namespace std;
 
const int K = 450;
 
void solve() {
    int n, q;
    cin >> n >> q;
 
    vector<int> f(n, -1); // f[i] = -1 if impossible, 1 if i = a^2, 2 if i = a^2 + b^2
    for (int a = 1; a * a < n; a++) {
        for (int b = a; a * a + b * b < n; b++) {
            f[a * a + b * b] = 2;
        }
        
        f[a * a] = 1;
    }
    
    vector<int> g(n, -1); // g[i] = -1 if impossible, else min `b` over i = a^2 - b^2
    for (int b = 1; b * b < n; b++) {
        for (int a = b; a * a - b * b < n; a++) {
            int v = a * a - b * b;
            if (g[v] < 0) g[v] = b * b;
        }
    }
    
    while (q--) {
        int a, b;
        cin >> a >> b;
        
        int ans = 4;
        for (int d = -K; d <= K; d++) {
            int x = a + abs(d) * d;
            if (x <= 0 || x > n) continue;
            
            int ta = x, tb = b;
            if (ta > tb) swap(ta, tb);
            
            int tans = 4;
            {
                int v = tb - ta;
                if (g[v] > 0 && g[v] <= max(n - tb, ta - 1)) {
                    tans = 2;
                }
                
                if (f[v] > 0) {
                    tans = f[v];
                }
                
                if (d != 0) tans++;
            }
            
            ans = min(ans, tans);
        }
        
        cout << ans << nl;
    }
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}