#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 998244353

void solve()
{
    int n;
    cin>>n;

    string s;
    cin>>s;

    vector<int>a,o,b;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='a') a.pub(i);
        if(s[i]=='b') b.pub(i);
        if(s[i]=='o') o.pub(i);
    }

    for(auto i :a) cout<<i+1<<" ";
    cout<<"\n";

    for(auto i :b) cout<<i+1<<" ";
    cout<<"\n";

    for(auto i :o) cout<<i+1<<" ";
    cout<<"\n";
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
    }
}

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007

void solve()
{
    int a,b;
    cin>>a>>b;

    cout<< a+b+7 << "\n";
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{ 
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    long long int T;
    cin>>T;
 
    while(T--)
    {
        long long int N,k,a,b;
        long long int minimum=1e18;
        cin>>N>>k>>a>>b;
        long long int friends[N],diff;
        for(long long int j=0;j<N;j++)
        {
            cin>>friends[j];
            diff=abs(a-friends[j]) + abs(b-friends[j]);
            minimum=min(minimum,diff);
        }
        cout<< minimum <<endl;
 
 
    }
 
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007

void solve()
{
    int n; cin >> n;
    int a[n];
    for(int i=0; i<n; i++){
      cin >> a[i];
      if(a[i] >=0) a[i] = -a[i]-1;
    }
    int ans = 1;
    if(n%2==0){
       for(int i=0; i<n; i++){
          a[i] = abs(a[i]);
          ans = (ans*a[i])%mod;
       }
       cout << ans%mod << endl;
    }
    else{
      sort(a,a+n);
      a[0] = -a[0]-1;
      for(int i=0; i<n; i++){
         a[i] = abs(a[i]);
        ans = (ans*a[i])%mod;
      }
      cout << ans%mod << endl;
    }

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
    }
}

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 998244353

void solve()
{
    int n; cin >> n;
    int a=0,b=0;
    for(int i=0; i<n; i++){
      int x,y,z; cin >> x >> y >> z;
      if(x==1){
         ya;
         a = y; b= z;
      }
      else{
        int mn1 = min(a,b);
        int mx1 = max(a,b);
        int mn2 = min(y,z);
        int mx2 = max(y,z);
        if(y==z){
            ya; a=y; b=z; continue;
        }
        if(mn2 >= mx1){
            na; continue;
        }
        ya;
        if(a==mx1) {a = mx2; b = mn2;}
        else{a = mn2; b = mx2;}
      }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
    }
}

#include <cmath>
#include<bits/stdc++.h>

using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<b; ++i)
#define all(x) x.begin(),x.end()

const long long INF=1e18;
const int32_t M=1e9+7;
const int32_t MM=998244353;

void solve()
{
  int n; cin >> n;
  int s[n];
  for(int i=0; i<n; i++) cin >> s[i];
  map<int,int> m;
  int ans = 0;
  for(int i = n-1; i>=1; i--){
    if(s[i]==s[i-1]){
        int x = n-1-i-m[s[i]];
        m.clear();
        ans += x;
        m[s[i]] += n-1-i;
    }
    m[s[i]]++;
  }
  cout << ans << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1; cin >> t;
    while(t--) solve();
    return 0;
}

/*
Mantra's code :)
*/

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007

int sof(int x)
{
    if(x/10==0) return x;

    int ans=0;
    while(x>0)
    {
        ans+=x%10;
        x/=10;
    }

    return sof(ans);
}

void solve()
{
    int n;
    cin>>n;

    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }

    int ans=sof(a[0]);
    for(int i=1;i<n;i++)
    {
        ans*=a[i];
        ans=sof(ans);
    }

    cout<<ans<<"\n";
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
    }
}

/*
Mantra's code :)
*/

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007

int sof(int x)
{
    if(x/10==0) return x;

    int ans=0;
    while(x>0)
    {
        ans+=x%10;
        x/=10;
    }

    return sof(ans);
}

void solve()
{
    int n;
    cin>>n;

    int flag0=0;
    int flag1=0;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]==0) flag0=1;
        if(i>0 && a[i]>1) flag1=1;
    }

    if(flag0)
    {
        cout<<"1\n";
        return;
    }

    int x=sof(a[0]);

    if(n==1)
    {
        cout<<x<<"\n";
        return;
    }

    if(x==0 || x==1 || x==9)
    {
        cout<<x<<"\n";
    }
    
    if(x==6 || x==3)
    {
        if(flag1==0)
        {
            cout<<x<<"\n";
        }
        else
        {
            cout<<"9\n";
        }
    }

    if(x==8)
    {
        int rem=a[1]%2;
        for(int i=2;i<n;i++)
        {
            rem*=(a[i]%2);
        }

        if(rem==0) cout<<"1\n";
        else cout<<"8\n";
    }

    if(x==4 || x==7)
    {
        int rem=a[1]%3;
        for(int i=2;i<n;i++)
        {
            rem*=(a[i]%3);
            rem%=3;
        }

        if(rem==2) cout<<(x==4 ? 7 : 4)<<"\n";
        if(rem==1) cout<<(x==4 ? 4 : 7)<<"\n";
        if(rem==0) cout<<(x==4 ? 1 : 1)<<"\n";
    }

    if(x==2 || x==5)
    {
        int rem=a[1]%6;
        for(int i=2;i<n;i++)
        {
            rem*=(a[i]%6);
            rem%=6;
        }

        if(rem==5) cout<<(x==2 ? 5 : 2)<<"\n";
        if(rem==4) cout<<(x==2 ? 7 : 4)<<"\n";
        if(rem==3) cout<<(x==2 ? 8 : 8)<<"\n";
        if(rem==2) cout<<(x==2 ? 4 : 7)<<"\n";
        if(rem==1) cout<<(x==2 ? 2 : 5)<<"\n";
        if(rem==0) cout<<(x==2 ? 1 : 1)<<"\n";
    }

    return;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
    }
}

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007

#define Fact_Length 500001 //Max length here is 519160
/**Takes a&b as input and Returns : The power (a,b), (a^b)%mod **/
int Power(int a,int b)
{
int result=1; a%=mod;
while(b) { if(b%2==1) result*=a; a*=a; a%=mod; result%=mod; b/=2; }
return result;
}
/** It give the modulo inverse of a, (1/a)%mod **/
int Mod_Inv(int a)
{
a%=mod; a=Power(a,mod-2); return a;
}
int Factorial[Fact_Length];
/** It make the above Factorial array to i! array**/
int Make_Factorial()
{
Factorial[0]=1;
for(int i=1;i<Fact_Length;i++) { Factorial[i]=i*Factorial[i-1]; Factorial[i]%=mod; } return 0;
}
int Implement_Make_Factorial=Make_Factorial(); //To Implement Make_Factorial

void solve()
{
    string s;
    cin>>s;

    int n=s.size();

    int freq[26]={0};
    for(int i=0;i<n;i++)
    {
        freq[s[i]-'a']++;
    }

    int inc=Factorial[n];
    for(int j=0;j<26;j++)
    {
        inc*=Mod_Inv(Factorial[freq[j]]);
        inc%=mod;
    }

    int ans=0;
    for(int i=0;i<n;i++)
    {
        if(i!=0)
        {
            inc*=freq[s[i-1]-'a']+1;
            inc%=mod;
        }
        inc*=Mod_Inv(n-i);
        inc%=mod;

        for(int j=0;j<s[i]-'a';j++)
        {
            int cur_inc=inc*freq[j];
            cur_inc%=mod;
            ans+=cur_inc;
            ans%=mod;
        }

        freq[s[i]-'a']--;

    }

    cout<<(ans+1)%mod<<"\n";
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
    }
}

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007

void solve()
{
    int n;
    cin>>n;

    int t[n];
    for(int i=1;i<n;i++)
    {
        cin>>t[i];
    }
    t[0]=0;

    int cur=0;
    for(int i=n-1;i>0;i--)
    {
        int delta=t[i]-t[i-1];
        delta%=(n-i+1);
        int prev=(cur+1+(n-i+1)-delta)%(n-i+1);
        cur=prev;
    }

    cout<<cur+1<<"\n";
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
    }
}

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define endl "\n"
#define sz(a) (int)a.size()
const ll mod = 1000000007;

#define NN 1000001

#define Fact_Length 500001 //Max length here is 519160

/**Takes a&b as input and Returns : The power (a,b), (a^b)%mod **/
ll Power(ll aaa,ll bbb)
{
ll result=1; aaa%=mod;
while(bbb) { if(bbb%2==1) result*=aaa; aaa*=aaa; aaa%=mod; result%=mod; bbb/=2; }
return result;
}

/** It give the modulo inverse of a, (1/a)%mod **/
ll Mod_Inv(ll aaa)
{
aaa%=mod; aaa=Power(aaa,mod-2); return aaa;
}

bool prime_chk[NN];
vector<ll> p;
int sieve()
{
    for(ll i=2;i<NN;i++)
    {
        prime_chk[i]=true;
    }
    prime_chk[0]=false;
    prime_chk[1]=false;
    for(ll i=2;i<NN;i++)
    {
        if(prime_chk[i]==true)
        {
            p.push_back(i);
            for(ll j=i*i;j<NN;j+=i)
            {
                prime_chk[j]=false;
            }
        }
    }
    return(0);
}

void solv()
{
    ll a,m;
    cin>>a>>m;
    map<ll,ll> ap, mp;

    ll t1=a,i=0;
    while(t1>1 && i<sz(p))
    {
        while(t1%p[i]==0)
        {
            ap[p[i]]++;
            t1/=p[i];
        }
        i++;
    }

    ll t2=m;i=0;
    while(t2>1 && i<sz(p))
    {
        while(t2%p[i]==0)
        {
            mp[p[i]]++;
            t2/=p[i];
        }
        i++;
    }

    ll ans=1, pro=1,c=1;

    ll tt;
    for(ll i=0; i<sz(p); i++)
    {
        if(ap[p[i]]>mp[p[i]])
        {
            pro*=Power(p[i],ap[p[i]]);
            pro%=mod;
        }
        else if(mp[p[i]]>0)
        {
            tt=Power(p[i],mp[p[i]]+1)-1+mod;
            tt*=Mod_Inv(p[i]-1);
            tt%=mod;
            ans*=tt;
            ans%=mod;
            c*=mp[p[i]]+1;
            c%=mod;
        }
    }

    if(t1!=t2)
        pro*=t1%mod;
    if(t2!=1)
    {
        ans*=(t2+1)%mod;
        c*=2;
        c%=mod;
    }
    ans%=mod, pro%=mod;

    ll ff=(ans)*(pro)-(c)*(a%mod)+mod*mod;
    ff%=mod;
    cout<<ff<<endl;
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll test_cases=sieve();
    cin>>test_cases;
    for(ll loop_var=1;loop_var<=test_cases;loop_var++)
    {
        solv();
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define sz(a) (int)(a.size())
const int mod = 1000000007;

/**Takes a&b as input and Returns : The power (a,b), (a^b)%mod **/
int Power(int aaa,int bbb)
{
int result=1; aaa%=mod;
while(bbb) { if(bbb%2==1) result*=aaa; aaa*=aaa; aaa%=mod; result%=mod; bbb/=2; }
return result;
}

/** It give the modulo inverse of a, (1/a)%mod **/
int Mod_Inv(int aaa)
{
aaa%=mod; aaa=Power(aaa,mod-2); return aaa;
}

int gcd(int a, int b)
{
    if(b==0)
        return a;
    return gcd(b, a%b);
}

int sum_pwr(int b,int p)       //Computes b+b^2+b^3+...+b^p
{
    int ans;
    if(b==1)
    {
        ans=p%mod;
        return ans;
    }

    ans=Power(b,p+1)-1+mod; ans%=mod;
    ans*=Mod_Inv(b-1);      ans%=mod;
    ans+=mod-1;             ans%=mod;
    return ans;
}

int AGP(int b,int p)       //Computes 1b+ 2(b^2) + 3(b^3) +...+ p(b^p)
{
    int ans;
    if(b==1)
    {
        p%=mod;
        ans=p*(p+1);            ans%=mod;
        ans*=Mod_Inv((int)2);   ans%=mod;
        return ans;
    }

    int tmp=(p%mod)*Power(b,p+1);   tmp%=mod;
    tmp+=mod-sum_pwr(b,p);          tmp%=mod;
    tmp*=Mod_Inv(b-1);

    ans=tmp%mod;
    return ans;
}

void solv()
{
    int n,a,b;
    cin>>n>>a>>b;
    int gc = gcd(a,b);
    if(n>=a+b)
    {
        n/=gc;
        int b1=Power(2,gc), b2=Power(5,gc),ans=0, tmp;

        ans+=sum_pwr(b1,n); ans%=mod;
        ans+=sum_pwr(b2,n); ans%=mod;

        tmp=AGP(b1,n)+AGP(b2,n);    tmp%=mod;
        tmp*=(3*gc)%mod;            tmp%=mod;

        ans+=tmp;
        ans%=mod;

        cout<<ans<<endl;
        return;
    }

    n = n/gc;
    a = a/gc;
    b = b/gc;

    vector<int> vi(n+1,0);
    queue<int> lvl;
    if(n>=a)
    {
        lvl.push(a);
        vi[a]=1;
    }
    if(n>=b && !vi[b])
    {
        lvl.push(b);
        vi[b]=1;
    }

    vector<int> save;
    int lvl_rn,cnt=0;
    while(!lvl.empty())
    {
        cnt++;
        lvl_rn=lvl.front();
        save.push_back(lvl_rn);
        lvl.pop();

        if(lvl_rn+a<=n && !vi[lvl_rn+a])
        {
            lvl.push(lvl_rn+a);
            vi[lvl_rn+a]=1;
        }
        if(lvl_rn-a>0 && !vi[lvl_rn-a])
        {
            lvl.push(lvl_rn-a);
            vi[lvl_rn-a]=1;
        }

        if(lvl_rn+b<=n && !vi[lvl_rn+b])
        {
            lvl.push(lvl_rn+b);
            vi[lvl_rn+b]=1;
        }
        if(lvl_rn-b>0 && !vi[lvl_rn-b])
        {
            lvl.push(lvl_rn-b);
            vi[lvl_rn-b]=1;
        }
    }

    int ans=0,cc;
    int b1=Power(2,gc),b2=Power(5,gc);
    for(int i=0; i<sz(save); i++)
    {
        cc=Power(b1,save[i])+Power(b2,save[i]); cc%=mod;
        cc*=(1+3*save[i]*gc)%mod;               cc%=mod;
        ans+=cc;                                ans%=mod;
    }

    cout<<ans<<endl;
    return;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int test_cases=1;
    //cin>>test_cases;
    for(int loop_var=1;loop_var<=test_cases;loop_var++)
    {
        solv();
    }
    return 0;
}