D. Ceil Divisions SOLUTION Code Forces

by

D. Ceil Divisions SOLUTION CodeForces

Educational Codeforces Round 101 (Rated for Div. 2)

You have an array a1,a2,…,an where ai=i.

In one step, you can choose two indices x and y (x≠y) and set ax=⌈axay⌉ (ceiling function).

Your goal is to make array a consist of n−1 ones and 1 two in no more than n+5 steps. Note that you don’t have to minimize the number of steps.

 

Input

The first line contains a single integer t (1≤t≤1000) — the number of test cases.

The first and only line of each test case contains the single integer n (3≤n≤2⋅105) — the length of array a.

It’s guaranteed that the sum of n over test cases doesn’t exceed 2⋅105.

 

Output

For each test case, print the sequence of operations that will make a as n−1 ones and 1 two in the following format: firstly, print one integer m (m≤n+5) — the number of operations; next print m pairs of integers x and y (1≤x,y≤n; x≠y) (x may be greater or less than y) — the indices of the corresponding operation.

It can be proven that for the given constraints it’s always possible to find a correct sequence of operations.

 

Example

input

2

3

4

output

2

3 2

3 2

3

3 4

4 2

4 2

Note

In the first test case, you have array a=[1,2,3]. For example, you can do the following:

choose 3, 2: a3=⌈a3a2⌉=2 and array a=[1,2,2];

choose 3, 2: a3=⌈22⌉=1 and array a=[1,2,1].

You’ve got array with 2 ones and 1 two in 2 steps.

 

In the second test case, a=[1,2,3,4]. For example, you can do the following:

choose 3, 4: a3=⌈34⌉=1 and array a=[1,2,1,4];

choose 4, 2: a4=⌈42⌉=2 and array a=[1,2,1,2];

choose 4, 2: a4=⌈22⌉=1 and array a=[1,2,1,1].

SOLUTION:
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
double a[300000];int t, n, b[300000], c[300000], ans;
int main() {
cin >> t;
while (t–) {
cin >> n;
ans = 0;
fo(i, 1, n)a[i] = i;
int k = ceil(sqrt(a[n]));
k = ceil(sqrt(k));
fo(i, 3, n – 1) {
if (a[i] == k)continue;
b[ans] = i;
c[ans++] = n;
}
while (a[n] > 1 ) {
 
b[ans] = n;
c[ans++] = k;
a[n] = ceil(a[n] / a[k]);
}
while (a[k]>1&&k!=2) {
b[ans] = k;
c[ans++] = 2;
a[k] = ceil(a[k] / a[2]);
}
cout << ans << endl;
fo(i, 0, ans-1 ) {
cout << b[i] << ” ” << c[i] << endl;
}
}
 
 
return 0;
}

Leave a Comment