#include #pragma GCC optimize("Ofast") #pragma GCC oprimize("unrol-loops") #define vec vector #define fi first #define se second #define all(x) (x).begin(), (x).end() #define int long long using namespace std; typedef pair pii; const int inf = 2e18; int mod = 1e9 + 7; void solve(){ int n; cin>>n; int ans = 1; if(n == 2){ cout << 1 << "\n"; return; } for(int i = 0;i