Check if $$$i$$$-th bit of the cost can be $$$0$$$?

Let's say the cost $$$2^{30} - 1$$$, we will try to set the $$$i$$$-th bit of the cost to $$$0$$$ while iterating $$$i$$$ from $$$29$$$ to $$$0$$$.

You can pick an index $$$i$$$ in your subsequence if $$$a_i$$$ is a sub-mask of the cost you are currently constructing.
Now greedily club indices that have distance $$$\leq k$$$ between them. Note that if you can make a subsequence we length $$$l'$$$, $$$(l' \gt l)$$$, you also make a subsequence with length $$$l$$$ (simply delete starting or the ending indexes of the subsequence).

If the length of any of these group of indices is greater than or equal $$$l$$$, you can set the corresponding bit to $$$0$$$ in cost.

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
void solve(){
    int n, k, l;
    cin >> n >> k >> l;
    vector<int> a(n);
    for(auto &x: a) cin >> x;
 
    int mask = (1ll << 32) - 1;
    
    vector<vector<int>> subsequences;
 
    vector<int> dummy;
    for(int i = 0; i < n; i++) dummy.push_back(i);
    subsequences.push_back(dummy);
 
    for(int bit = 31; bit >= 0; bit--) {
        mask ^= (1ll << bit);
        vector<vector<int>> new_subsequences;
 
        for(auto &x: subsequences) {
            vector<int> current;
            for(int i = 0; i < x.size(); i++) {
                if((a[x[i]] | mask) == mask) {
                    current.push_back(x[i]);
                }
            }   
 
            if(current.size() == 0) continue;
 
            vector<int> carry;
            carry.push_back(current[0]);
 
            int lst = current[0];
            for(int i = 1; i < current.size(); i++) {
                if(current[i] - lst > k) {
                    if(carry.size() >= l) 
                        new_subsequences.push_back(carry);
                    carry.clear();
                }
                carry.push_back(current[i]);
                lst = current[i];
            }
            if(carry.size() >= l) new_subsequences.push_back(carry);
        }
 
        if(new_subsequences.size()) {
            swap(subsequences, new_subsequences);
        }
        else {
            mask ^= (1ll << bit);
        }
    }   
 
    int ans = a[subsequences[0][0]];
    for(int i = 1; i < subsequences[0].size(); i++) {
        ans |= a[subsequences[0][i]];
        assert(subsequences[0][i] - subsequences[0][i - 1] <= k); 
    }
    assert(ans == mask);
    assert(subsequences[0].size() >= l);
    cout << mask << "\n";
}   
 
int32_t main() {    
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
    int t = 1; 
    cin>>t;
    while(t--) solve();
}

Try using dynamic programming

We can solve this problem using 2D DP. Let $$$dp[i][j]$$$ return the number of favourable outcomes where $$$i$$$ is the number of the game to be played and $$$j$$$ is 1 if Harsh is playing the game else 0. if Harsh's crush is watching, Harsh must play and win the game -

$$$dp[i][0] = 0$$$ $$$dp[i][1] = dp[i + 1][1]$$$

if Harsh's crush is not watching -

$$$dp[i][1] = dp[i + 1][1] + dp[i + 1][0]$$$ $$$dp[i][0] = 2 * dp[i + 1][1]$$$

#include <bits/stdc++.h>

using namespace std;

#ifndef ONLINE_JUDGE
    #include "debug.h"
#else
    #define debug(x) 
#endif

#define MOD 1000000007
#define INF 1e18
#define endl "\n"
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define int long long

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

    std::vector<int> v(m), crush(n);
    for(auto &x: v) {
        cin >> x;
        crush[x - 1] = 1;
    }

    vector<vector<int>> dp(n, vector<int>(2));

    if(crush[n - 1]) {
        dp[n - 1][1] = 1;
        dp[n - 1][0] = 0;
    }
    else {
        dp[n - 1][1] = dp[n - 1][0] = 2;
    }

    for(int i = n - 2; i >= 0; i--) {
        if(crush[i]) {
            dp[i][0] = 0;

            dp[i][1] = dp[i + 1][1];
        }
        else {
            dp[i][0] = (2 * dp[i + 1][1]) % MOD;

            dp[i][1] = (dp[i + 1][1] + dp[i + 1][0]) % MOD;
        }
    }

    cout << dp[0][1] << endl;
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int tt = 1;
    cin >> tt;
    while(tt--) {
        solve();       
    }
    return 0;
}

Is there any benefit of taking a subarray which contains more than 2 occurence of val?

Let us prove that the answer is an subarray which contains only two occurence of val, where the first and last element are val.
Firstly, any subarray which does not contain val as first/last element is not optimal as this subarray can be trimmed to such a state which improves the ratio.
Let $$$a$$$ be the smallest distance between any two occurrence of val in the array. The answer for this subarray is 2/(a+2).
It is easy to see that adding any occurence at a distance >$$$a$$$ can never give better answer.
Now it is needed to prove that adding more occurence at distance $$$a$$$ also does not improve the answer.
Let us add y occurence of val at a distance $$$a$$$.
The new ratio is (2 + y ) / (y*a + y + 2).
If this ratio is better, (2 + y ) / (y*a + y + 2 + a) > 2 / a+2
2*a + y*a + 2*y + 4 > 2*y*a + 2y + 4 + 2*a
0 > y*a
0 > y
By contradiction, it is shown that we must not add any more occurrences.

//Author Solution
#include<bits/stdc++.h>
using namespace std;
int32_t main()
{
 ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
map<int,set<int>>m;
map<int,set<pair<int,int>>>track;
int a[n+1];
for(int i=0;i<n;i++)
{
    int x;
    cin>>x;
    a[i]=x;
    m[x].insert(i);
}
for(auto &it:m)
{
    int temp=-1;
    for(auto &trav:it.second)
    {
        if(temp==-1)
        temp=trav;
        else
        {
            track[it.first].insert({trav-temp,temp});
            temp=trav;
        }
    }
}
int q;
cin>>q;
while(q--)
{
    int check;
    cin>>check;
    if(check==1)
    {
        int x;
        cin>>x;
        if(track[x].empty())
        {
            cout<<-1<<'\n';
            continue;
        }
        auto it=*track[x].begin();
        cout<<it.second<<" "<<it.second+it.first<<endl;
    }
    else
    {
        int indx,y;
        cin>>indx>>y;
        int temp=a[indx];
        auto it=m[temp].find(indx);
        int left=-1,right=-1;
        if(it!=m[temp].begin())
        {
            auto it1=it;
            it1--;
            left=(*it1);
            track[temp].erase(track[temp].find({((*it)-(*it1)),(*it1)}));
        }
        auto it1=it;
        it1++;
        if(it1!=m[temp].end())
        {
            right=(*it1);
            track[temp].erase(track[temp].find({((*it1)-(*it)),(*it)}));
              
        }
        if(left!=-1&&right!=-1)
        {
            track[temp].insert({right-left,left});
        }
        m[temp].erase(it);
        m[y].insert(indx);
        
        it=m[y].find(indx);
        left=-1,right=-1;
        if(it!=m[y].begin())
        {
            auto it1=it;
            it1--;
            track[y].insert({((*it)-(*it1)),(*it1)});
            left=(*it1);
        }
        it1=it;
        it1++;
        if(it1!=m[y].end())
        {
              track[y].insert({((*it1)-(*it)),(*it)});
              right=(*it1);
        }
        a[indx]=y;
        if(left!=-1&&right!=-1)
        {
            track[y].erase(track[y].find({right-left,left}));
        }
    }
}
 return 0;
}

//Another solution
#include<bits/stdc++.h>
using namespace std;
vector<int>a;
unordered_map<int,set<int>>m1;
unordered_map<int,multiset<pair<int,pair<int,int>>>>m2;
void query1(int value){
    if(m2.count(value)==0){
        cout<<-1<<endl;return;
    }
    cout<<m2[value].begin()->second.first<<' '<<m2[value].begin()->second.second<<endl;
}
 
void query2(int x,int y){
    auto it=m1[a[x]].find(x);auto it1=it,it2=it;
    if(it1!=m1[a[x]].begin()){
        it1--;
        m2[a[x]].erase({*it-*it1,{*it1,*it}});
    }
    if(it2!=(--m1[a[x]].end())){
        it2++;
        m2[a[x]].erase({*it2-*it,{*it,*it2}});
    }
    if(it2!=it&&it1!=it)
    {
        m2[a[x]].insert({*it2-*it1,{*it1,*it2}});
    }
    m1[a[x]].erase(it);
    if(m1[a[x]].size()==0)m1.erase(a[x]);
    if(m2[a[x]].size()==0)m2.erase(a[x]);
    a[x]=y;
    m1[y].insert(x);
    it=m1[y].find(x);it1=it,it2=it;
    if(it1!=m1[y].begin()){
        it1--;
        m2[a[x]].insert({*it-*it1,{*it1,*it}});
    }
    if(it2!=(--m1[y].end())){
        it2++;
        m2[a[x]].insert({*it2-*it,{*it,*it2}});
    }
     if(it2!=it&&it1!=it)
    {
        m2[a[x]].erase({*it2-*it1,{*it1,*it2}});
    }
    
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    a.resize(n);
    for(int &it:a)cin>>it;
    for(int i=0;i<n;i++){
        m1[a[i]].insert(i);
    }
    for(auto &it:m1){
        multiset<pair<int,pair<int,int>>>&itr=m2[it.first];
        vector<int>temp(it.second.begin(),it.second.end());
        for(int i=0;i+1<temp.size();i++){
            itr.insert({temp[i+1]-temp[i],{temp[i],temp[i+1]}});
        }
    }
    int q;cin>>q;
    for(int i=0;i<q;i++){
        int type;cin>>type;
        if(type==1){
            int x;cin>>x;
            query1(x);
        }else{
            int x,y;cin>>x>>y;
            query2(x,y);
        }
    }
}

Pbds

Let Array $$$B$$$ store indices of an element x in the array.
For two indices i and j where i < j, if A[i..j] is good, then (j-i+1)/(A[j]-A[i]+1)>=K/1000.
1000*j-A[j]>=1000*i-A[i]+K-1
For each index we can find the number of indices which make a good subarray by using pbds or segment tree.

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define ll __int128
using namespace __gnu_pbds;
using namespace std;
typedef tree<pair<long double,int>, null_type,
      less<pair<long double,int>>, rb_tree_tag,
      tree_order_statistics_node_update>
      Pbds;


const char nl = '\n';
bitset<1000010> iscomp;
int highest[1000010];
void sieve()
{
    for (int i = 2; i < 1000010; i++)
    {
        if (!iscomp[i])
        {
            highest[i]=i;
            for (int j = i * i; j < 1000010; j += i)
            {
                highest[j]=i;
                iscomp[j] = 1;
            }
        }
    }
}
int n,k;
void yes() { cout << "Yes" << endl; }
void no() { cout << "No" << endl; }
void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void solve(int testcase)
{
    cin>>n>>k;
    vector<int>a(n);
    for(int &it:a)cin>>it;
    map<int,vector<int>>m;
    for(int i=0;i<n;i++){
        m[a[i]].push_back(i);
    }
    long double K=k;
    for(auto &it:m){
        cout<<it.first<<' ';
        if(it.second.size()==1){
            cout<<0<<endl;continue;
        }
        Pbds s;
        s.insert({K-1000-K*it.second[0],0});
        int ans=0;
        for(int i=1;i<it.second.size();i++){
            int p=s.order_of_key({i*1000-K*it.second[i],INT_MAX});
            ans+=p;
            s.insert({K-1000-K*it.second[i]+i*1000,i});
        }
        cout<<ans<<' ';
        cout<<endl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //sieve();
    int t = 1;
    //cin >> t;
    for (int p = 1; p <= t; p++)
    {
        solve(p);
    }
}

Try doing something with the lowest common ancestor of $$$i$$$ and $$$i + 1$$$.

Prefix sums on tree?

Since we have to answer the problem offline, let's try to do something similar to difference arrays.

First root the tree on an arbitrary vertex — say $$$1$$$.

Say the lowest common ancestor of $$$i$$$ and $$$i + 1$$$ be $$$LCA$$$. We will add $$$1$$$ to $$$score[parent_i]$$$ and $$$score[i + 1]$$$, and subtract $$$1$$$ from $$$score[LCA]$$$ and $$$score[parent_{LCA}]$$$. A Now if we add up scores going from bottom to top, we will get the number of times each vertex is visited.

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

#define int long long

// LCA code source - usaco.guide
int depth[200010];
int up[200010][20];
int score[200010];
vector<int> adj[200010];

void dfs(int v) {
    for(int i = 1; i < 20; i++) { up[v][i] = up[up[v][i - 1]][i - 1]; }
    for (int x : adj[v]) {
        if (x != up[v][0]) {
            depth[x] = depth[up[x][0] = v] + 1;
            dfs(x);
        }
    }
}

int jump(int x, int d) {
    for(int i = 0; i < 20; i++) {
        if ((d >> i) & 1) x = up[x][i];
    }
    return x;
}

int LCA(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);

    a = jump(a, depth[a] - depth[b]);
    if (a == b) return a;

    for(int i = 19; i >= 0; i--) {
        int aT = up[a][i], bT = up[b][i];
        if (aT != bT) a = aT, b = bT;
    }

    return up[a][0];
}

void clear(int n) {
    for(int i = 0; i < n; i++) {
        score[i] = 0;
        depth[i] = 0;
        adj[i].clear();
        for(int j = 0; j < 20; j++) 
            up[i][j] = 0;
    }   
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        clear(n + 5);

        for(int i = 0; i < n - 1; i++) {
            int a, b; cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        dfs(1);

        for(int i = 1; i < n; i++) {
            int par = LCA(i, i + 1);
            score[up[i][0]]++, score[i + 1]++;
            score[par]--, score[up[par][0]]--;
        }
        
        vector<pair<int,int>> vp;
        for(int i = 2; i <= n; i++) {
            vp.push_back({-depth[i], i});
        }
        sort(vp.begin(), vp.end());

        for(int i = 0; i < vp.size(); i++) {
            score[up[vp[i].second][0]] += score[vp[i].second];
        }

        score[1]++; // initial stand
        for(int i = 1; i <= n; i++) cout << score[i] << " ";
        cout << "\n";
    }
    return 0;
}

try to calculate of what each character.

Can we do something with subsequence of $$$ab$$$ $$$bc$$$.

Lets solve this problem when there are no queries In that case we can solve this by iterating through string and and whenever we get current character as $$$b$$$ we will calculate number of $$$abc$$$ subsequences involving this current $$$b$$$ character which is

= number of $$$a$$$ occurred before our current character * number of $$$c$$$ occurred after our current character

hence for each $$$b$$$ character we will add this to our answer. Now lets calculate number of $$$abc$$$ subsequence contributed by each character

• s[i]='b' — number of $$$a$$$ occurrences before $$$ith$$$ index *number of $$$c$$$ occurrences after $$$ith$$$ index.

• s[i]='c' — number of subsequences of $$$ab$$$ before $$$ith$$$ index.

• s[i]='a' — number of subsequences of $$$bc$$$ after $$$ith$$$ index.

now we will decrease and increase this contribution according to changes occurred in query. Also we have to precompute number of $$$ab$$$ and $$$bc$$$ subsequences in order to get changes.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define debug(x) cout << #x << ' ' << x << endl;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define exe(k,n) for(int i=k;i<n;i++)
#define exec(n) for(int i=0;i<n;i++)
#define endl '\n'
#define ss second
#define ff first
#define pb push_back
#define hii cout << "Hi\n";
#define int long long int
const int N = 2e5+10;
const int M = 1e9+7;
const int inf=1e9;
signed main() 
{   fastio();       
    int T=1;
    cin >>T;
    while(T--)
    {   
       int n,q;
       cin >> n >> q;
       string s;
       cin >> s;
       vector<int> ab(n),bc(n),a(n),c(n);
       for(int i=1;i<n;i++)
       {
            ab[i]=ab[i-1];
            a[i]+=(a[i-1]+(int)(s[i-1]=='a'));
            if(s[i-1]=='b') ab[i]+=a[i];
       }
       for(int i=n-2;i>=0;i--)
       {
           bc[i]=bc[i+1];
           c[i]+=(c[i+1]+(int)(s[i+1]=='c'));
           if(s[i+1]=='b') bc[i]+=c[i];
       }
       int ans=0;
       for(int i=0;i<n;i++)
       {
            if(s[i]=='b')
            {
                ans+=a[i]*c[i];
            }
       }
       while(q--)
       {
            int ind;
            char cc;
            cin >> ind >> cc;
            ind--;
            int curr=ans;
            if(s[ind]=='b')
            {
                curr-=a[ind]*c[ind];
            }
            else if(s[ind]=='a')
            {
                curr-=bc[ind];
            }
            else
            {
                curr-=ab[ind];
            }
            if(cc=='a')
            {
                curr+=bc[ind];
            }
            else if(cc=='b')
            {
                curr+= a[ind]*c[ind];
            }
            else
            {
                curr+=ab[ind];
            }
            cout << curr << endl;
       }
    }       
 return 0;   
} 

Segment tree

We store count of “a” , “b” , “c” , “ab” , “bc” , “abc” subsequences in each node of the segment tree. Let $$$l.x$$$ denote count of subsequence of $$$x$$$ in left side of index To construct “a” (similar for “b” and “c”) subsequences we have 2 possibilities:

• Take “a” subsequence from left = $$$l.a$$$
• Take “a” subsequence from right = $$$r.a$$$

So , No. of “a” subsequences = $$$l.a$$$ + $$$r.a$$$ To construct “ab” (similar for “bc”) subsequences we have 3 possibilities:

• Take “ab” subsequence from left = $$$l.a$$$
• Take “ab” subsequence from right = $$$r.a$$$
• Take “a” subsequence from left and “b” subsequence from right = $$$l.a * r.b$$$

So , No. of “ab” subsequences = $$$l.ab + r.ab + l.a * r.b$$$

To construct “abc” subsequences we have 4 possibilities:

• Take “abc” subsequence from left = $$$l.abc$$$
• Take “ab” subsequence from left and “c” subsequence from right = $$$l.ab * r.c$$$
• Take “a” subsequence from left and “bc” subsequence from right = $$$l.a * r.bc$$$
• Take “abc” subsequence from right = $$$r.abc$$$

So , No. of “abc” subsequences = $$$l.abc + l.ab * r.c + l.a * r.bc + r.abc$$$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
 
struct node
{
    ll a,b,c;
    ll ab,bc;
    ll abc;
};
 
node combine(node l , node r)
{
    ll a = (l.a + r.a);
    ll b = (l.b + r.b);
    ll c = (l.c + r.c);
 
    ll ab = (l.ab + l.a*r.b + r.ab);
    ll bc = (l.bc + l.b*r.c + r.bc);
 
    ll abc = (l.abc + l.ab*r.c + l.a*r.bc + r.abc);
 
    return {a,b,c,ab,bc,abc};
}
 
class Segment_Tree
{
    public : 
 
    int n;
    vector<node> tree;
    node IDENTITY = {0,0,0,0,0,0};
 
    node single(char ch)
    {
        if(ch == 'a') return {1,0,0,0,0,0};
        if(ch == 'b') return {0,1,0,0,0,0};
        return {0,0,1,0,0,0};
    }  
 
    Segment_Tree(string &v)
    {
        this->n = v.size();
        tree.resize(4*n + 5);        
        build(1 , 0 , n-1 , v);
    }
 
    void build(int v, int lv, int rv , string &a)
    {
        if(lv == rv) {tree[v] = single(a[lv]); return;}
 
        int m = (lv+rv)/2;
        build(2*v , lv , m , a);
        build(2*v + 1, m+1 , rv , a);
        tree[v] = combine(tree[2*v],tree[2*v + 1]);
    }
 
    void set(int i, char x)
    {
        set(i , x, 1 , 0, n-1);
    }
 
    void set(int i, char x, int v, int lv ,int rv)
    {
        if(lv == rv) {tree[v] = single(x); return;}
 
        int m = (lv+rv)/2;
        if(i <= m) set(i,x, 2*v , lv , m);
        else set(i,x, 2*v + 1 , m+1 , rv);
        tree[v] = combine(tree[2*v],tree[2*v + 1]);
    }
 
    node query(int l, int r)
    {
        return query(l, r, 1, 0, n-1);
    }
 
    node query(int l, int r, int v, int lv, int rv)
    {
        if(r < lv or rv < l) return IDENTITY;
        if(l <= lv and rv <= r) return tree[v];
 
        int m = (lv+rv)/2;
        node left = query(l, r, 2*v, lv, m);
        node right = query(l, r, 2*v + 1, m+1, rv);
        return combine(left , right);
    }
};
 
int main()
{
    int t; cin >> t;
    while(t--)
    {
        int n,q; cin >> n >> q;
        string s; cin >> s;
        Segment_Tree st(s);
 
        while(q--)
        {
            int i; cin >> i; i--;
            char c;
            cin >> c;
            st.set(i,c);
            node ans = st.query(0,n-1);
            cout << ans.abc << '\n';
        }
    }
    return 0;
}

What will happen when two duplicate elements are present?

try solving the problem when all elements are distinct.

First thing to notice is that when multiple ball wants to go to same cell then only one ball can enter the cell hence if any $$$a_i$$$ occurs multiple times answer is only affected once. Now we will count number of distinct elements, when number of distinct element in array are not odd then Kshitij wins as for every ball picked by Milan, Kshitij will pick another ball. Hence if number of distinct elements are odd we need to ouput YES.

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

typedef long long ll;
typedef unsigned long long ull; 
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef map<int, int> mii;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvll;
#define f(i, a, b, j) for(int i = int(a); i < int(b); i = i + int(j))
#define M map
#define V vector
#define P pair
#define all(a) a.begin(), a.end() 
#define rall(a) a.rbegin(), a.rend() 
#define nl "\n"
#define pb push_back
#define mp make_pair
#define reset(a, b) memset(a, int(b), sizeof(a))
#define MOD1 (ll)1000000007
#define MOD2 (ll)998244353
#define INF (int)2e9

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) { 
        int n;
        cin >> n;
        set<int> s;
        for(int i=0;i<n;i++)
        {
            int a;
            cin >> a;
            s.insert(a);
        }
        int sz=s.size();
        if(sz&1) cout << "YES";
        else cout << "NO";
        cout << endl;
    }
    return 0;
}

find the groups in which you and your crush are placed .

use ceil function .

As you want that you and your crush will be in same group , for that find out Group number for both $$$G_a= ceil(a/x)$$$ (group number where you are placed) , $$$G_b = ceil(b/x)$$$ (group number where your crush is placed) . there are total of $$$n$$$ different value of $$$x$$$ (group size) which is equiprobable. Hence $$$Probability = P/Q$$$ . $$$P$$$ = Number of group size's in which $$$G_a = G_b , Q = n$$$ .

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

#define int long long
#define pb push_back
#define ppb pop_back
#define MOD 998244353

const int N=1e5;

int binexp(int a, int b) {
    int res = 1;
    while (b > 0) {
        if(b&1)
        res = ((res%MOD)*(a%MOD))%MOD;
        a = ((a%MOD)*(a%MOD))%MOD;
        b >>= 1;
    }
    return res;
}

void solve(){
    int n;
    string a,b;
    cin >> n >> a >> b;
    int an = stoi(a.substr(7,3));
    int bn = stoi(b.substr(7,3));
    int ans = 0;
    for(int i=1;i<=n;i++){
        if((an-1)/i == (bn-1)/i){
            ans++;
        }
    }
    
    ans *= binexp(n,MOD-2);
    ans %= MOD;

    cout << ans << endl;

}

int32_t main()
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

#ifndef ONLINE_JUDGE
    freopen("test0.in", "r", stdin);
    freopen("test0.out", "w", stdout);
#endif

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