• Vì các toán hạng có thể có nhiều chữ số, hoặc là số âm nên ta sẽ coi mỗi toán tử/toán hạng là một xâu ký tự. Như vậy, ta sẽ nhập vào một mảng gồm $$$n$$$ xâu ký tự, rồi xử lý giống như bài ở trên Code PTIT.

• Ở đây, để kiểm tra một xâu đang duyệt đến có là "số" hay không thì ta chỉ cần kiểm tra ký tự cuối cùng của nó có là chữ số hay không ?

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

#define el '\n'
#define int long long

void solve(){
    int n; cin >> n;
    vector<string> v(n);
    for(auto &i : v) cin >> i;
    stack<int> st;
    for(int i=n-1; i>=0; i--){
        if(isdigit(v[i].back())){
            st.push(stoll(v[i]));
        }else{
            int x = st.top(); st.pop();
            int y = st.top(); st.pop();
            if(v[i] == "+"){
                st.push(x + y);
            }else if(v[i] == "*"){
                st.push(x * y);
            }else if(v[i] == "/"){
                st.push(x / y);
            }else st.push(x - y);
        }
    }
    cout << st.top() << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Vì các toán hạng có thể có nhiều chữ số, hoặc là số âm nên ta sẽ coi mỗi toán tử/toán hạng là một xâu ký tự. Như vậy, ta sẽ nhập vào một mảng gồm $$$n$$$ xâu ký tự, rồi xử lý giống như bài ở trên Code PTIT.

• Ở đây, để kiểm tra một xâu đang duyệt đến có là "số" hay không thì ta chỉ cần kiểm tra ký tự cuối cùng của nó có là chữ số hay không ?

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

#define el '\n'
#define int long long

void solve(){
    int n; cin >> n;
    vector<string> v(n);
    for(auto &i : v) cin >> i;
    stack<int> st;
    for(int i=0; i<v.size(); i++){
        if(isdigit(v[i].back())){
            st.push(stoll(v[i]));
        }else{
            int x = st.top(); st.pop();
            int y = st.top(); st.pop();
            if(v[i] == "+"){
                st.push(x + y);
            }else if(v[i] == "*"){
                st.push(x * y);
            }else if(v[i] == "/"){
                st.push(y / x);
            }else st.push(y - x);
        }
    }
    cout << st.top() << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Vì các toán hạng có thể có nhiều chữ số, hoặc là số âm nên ta sẽ coi mỗi toán tử/toán hạng là một xâu ký tự. Như vậy, ta sẽ nhập vào một mảng gồm $$$n$$$ xâu ký tự, rồi xử lý giống như bài ở trên Code PTIT.

• Ở đây, để kiểm tra một xâu đang duyệt đến có là "số" hay không thì ta chỉ cần kiểm tra ký tự cuối cùng của nó có là chữ số hay không ? Điều này sẽ giúp ta vừa kiểm tra được khi quyết định nhét nó vào stack cũng như là xác định biểu thức đã cho là tiền tố hay hậu tố.

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

#define el '\n'
#define int long long

void solve(){
	int n; cin >> n;
	string a[n+5];
	for(int i=1; i<=n; i++){
		cin >> a[i];
	}
	stack<int> st;
	if(isdigit(a[1].back())){
		for(int i=1; i<=n; i++){
			if(isdigit(a[i].back())){
				st.push(stoll(a[i]));
			}else{
				int x = st.top(); st.pop();
				int y = st.top(); st.pop();
				if(a[i] == "+"){
					st.push(x + y);
				}else if(a[i] == "-"){
					st.push(y - x);
				}else if(a[i] == "*"){
					st.push(x * y);
				}else{
					st.push(y / x);
				}
			}
		}
	}else{
		for(int i=n; i>=1; i--){
			if(isdigit(a[i].back())){
				st.push(stoll(a[i]));
			}else{
				int x = st.top(); st.pop();
				int y = st.top(); st.pop();
				if(a[i] == "+"){
					st.push(x + y);
				}else if(a[i] == "-"){
					st.push(x - y);
				}else if(a[i] == "*"){
					st.push(x * y);
				}else{
					st.push(x / y);
				}
			}
		}
	}
	cout << st.top() << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'
#define mxn 1000006

int dp[mxn];
 
void solve(){
    int n, m; cin >> n >> m;
    queue<int> q;
    q.push(n);
    while(!q.empty()){
        int x = q.front(); q.pop();
        if(x == m){
            cout << dp[x]; return;
        }
        if(x * 2 <= 1e6 and dp[x * 2] == 0){
            dp[x * 2] = dp[x] + 1;
            q.push(x * 2);
        }
        if(x - 1 >= 1 and dp[x - 1] == 0){
            dp[x - 1] = dp[x] + 1;
            q.push(x - 1);
        }
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Xâu $$$s$$$ có thể có dấu cách nên ngoài các cách nhập xâu có dấu cách mà bạn có thể đã biết, thì mình có $$$1$$$ cách sau đây cũng khá đơn giản mà cũng có tác dụng tương tự getline(cin >> ws, s) thì ws ở đây mình nghĩ có nghĩa là whitespace, thì nó cũng giúp việc cin xong getline không bị lỗi. Tuy nhiên, nếu không có cin trước cái getline này, thì mình không khuyến khích các bạn sử dụng vì nó có thể gây lỗi.

• Ở bài toán này, ta sẽ sử dụng ngăn xếp để xử lý. Về cơ bản, phần thuật sẽ khá giống với bài kiểm tra dãy ngoặc đúng, chỉ khác ở chỗ khi gặp dấu ( ta sẽ in ra số thứ tự nó xuất hiện và đẩy số thứ tự đó vào stack (mục đích là để khi gặp dấu đóng ngoặc tương ứng, ta cũng sẽ in ra được số thứ tự này). Như vậy, khi gặp dấu ) thì ta chỉ cần in ra số ở đầu stack và pop nó ra.

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

#define el '\n'

void solve(){
    string a; getline(cin >> ws, a);
    int n = a.size();
    stack<int> st;
    int x = 1;
    for(int i=0; i<n; i++){
        if(a[i] == '('){
            cout << x << ' ';
            st.push(x);
            ++x;
        }else if(a[i] == ')'){
            cout << st.top() << ' ';
            st.pop();
        }
    }
    cout << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

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

int n, a[1000006];

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    stack<int> st;
    for(int i=1; i<=n; i++){
        if(st.empty()){
            st.push(a[i]);
        }else{
            if((st.top() + a[i]) % 2 == 0){
                st.pop();
            }else st.push(a[i]);
        }
    }
    cout << st.size();
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

void LonggVuz(){
    int n, k; cin >> n >> k;
    int a[n+5];
    fo(i, 1, n) cin >> a[i];
    priority_queue<int, vec<int>, greater<int>> q;
    fo(i, 1, n) q.push(a[i]);
    int res = 0;
    while(len(q) > 1){
        if(len(q) >= k){
            int mx = -oo, mi = oo, sum = 0;
            fo(i, 1, k){
                int t = q.top(); q.pop();
                mx = max(mx, t);
                mi = min(mi, t);
                sum += t;
            }
            q.push(sum);
            res += mx - mi;
        }else{
            int mx = -oo, mi = oo, sum = 0;
            while(!q.empty()){
                int t = q.top(); q.pop();
                mx = max(mx, t);
                mi = min(mi, t);
                sum += t;
            }
            q.push(sum);
            res += mx - mi;
        }
    }
    cout << q.top() << ' ' << res;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

• Ta sẽ sử dụng hàng đợi để sinh ra đủ $$$2 \times 10^5$$$ các số có tổng chữ số bằng $$$10$$$, lưu các phần tử trong hàng đợi theo cặp {số, tổng chữ số} để đỡ phải tính toán nhiều lần. Ta sẽ duyệt các chữ số $$$[0, 9]$$$ kiểm tra xem việc nối chữ số đó vào cuối đã làm tổng chữ số vượt quá $$$10$$$ hay chưa, nếu chưa vượt quá $$$10$$$ thì ta tiếp tục đưa nó vào hàng đợi. Với mỗi phần tử ở đầu hàng đợi mà có tổng chữ số là $$$10$$$, ta sẽ nhét chúng vào một cái vector/mảng để trả lời cho các truy vấn.

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

#define pe pair<int, int>
#define fi first
#define se second
#define el '\n'
#define int long long

vector<int> v;
void pre(){
    queue<pe> q;
    for(int i=1; i<=9; i++){
        q.push({i, i});
    }
    while(1){
        pe x = q.front(); q.pop();
        int n = x.fi, s = x.se;
        if(s == 10){
            v.push_back(n);
            if(v.size() == 2e5) return;
        }
        for(int i=0; i<=9; i++){
            if(s + i <= 10){
                q.push({n * 10 + i, s + i});
            }else break;
        }
    }
}
 
void solve(){
    int n; cin >> n;
    cout << v[n - 1] << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    pre();
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

Ta sẽ xử lý bài toán này giống bài Giải mã xâu ký tự trên Code PTIT. Ý tưởng chính sẽ là phân tích hết các phân tử dạng nén ra thành nguyên tử, rồi sau đó cộng hết các giá trị đó và in ra kết quả.

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

#define el '\n'

int val(char c){
    // khối lượng nguyên tử
    if(c == 'C') return 12;
    if(c == 'O') return 16;
    return 1;
}
 
int it = 1;
void solve(){
    cout << "Test #" << it++ << ": ";
    string a; cin >> a;
    int n = a.size();
    stack<char> st;
    for(int i=0; i<n; i++){
        if(a[i] != ')'){
            // đang xét một phân tử có dạng nén
            // CH2O -> CHHO
            if(isdigit(a[i])){
                int times = a[i] - '0';
                for(int j=1; j<times; j++) st.push(st.top());
            }else st.push(a[i]);
        }else{
            // tính số lần nén, mặc định là 1
            int times = 1;
            if(i + 1 < n and isdigit(a[i + 1])) times = a[i + 1] - '0';
            // dịch thêm 1 chỉ số để bỏ qua "số lần lặp" vừa xét
            if(times > 1) ++i;
            // bắt đầu tìm công thức được lặp
            string s = "";
            while(!st.empty() and st.top() != '('){
                s += st.top();
                st.pop();
            }
            st.pop();
            // tạo ra công thức đầy đủ
            string str = "";
            while(times--) str += s;
            // rồi đưa lại vào ngăn xếp
            for(char &c : str) st.push(c);
        }
    }
    // tính toán kết quả
    int res = 0;
    while(!st.empty()){
        res += val(st.top());
        st.pop();
    }
    cout << res << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;



void LonggVuz(){
    int n; cin >> n;
    int a[n+5];
    fo(i, 1, n) cin >> a[i];
    vec<int> l(n + 1);
    {
        stack<int> st;
        fo(i, 1, n){
            while(!st.empty() and a[st.top()] <= a[i]) st.pop();
            if(st.empty()) l[i] = 0;
            else l[i] = st.top();
            st.push(i);
        }
    }
    vec<int> r(n + 1);
    {
        stack<int> st;
        fd(i, n, 1){
            while(!st.empty() and a[st.top()] < a[i]) st.pop();
            if(st.empty()) r[i] = n + 1;
            else r[i] = st.top();
            st.push(i);
        }
    }
    int res = 0;
    fo(i, 1, n){
        int le = l[i] + 1, ri = r[i] - 1;
        res += a[i] * (i - le + 1) * (ri - i + 1);
    }
    cout << res;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

Ta sẽ sử dụng hàng đợi để duyệt qua tất cả các số có thể gặp. Giống với thao tác đề bài cho, ta sẽ duyệt qua các cặp số có tích đúng bằng $$$n$$$, rồi tìm ra số mới và kiểm tra xem số đó đã được xét hay chưa ? Nếu chưa thì ta sẽ push nó vào hàng đợi rồi tiếp tục quá trình.

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

#define el '\n'
#define mxn 

void solve(){
    int n; cin >> n;
    map<int, int> mp; // đánh dấu các phần tử đã được xét
    queue<int> q;
    q.push(n); // bắt đầu quá trình
    while(!q.empty()){
        int x = q.front(); q.pop();
        int c = sqrtl(x);
        for(int u=1; u<=c; u++){
            // tìm các cặp số u, v
            if(x % u == 0){
                int v = x / u;
                int num = (u - 1) * (v + 1);
                if(!mp[num]){ // chưa xét
                    mp[num] = 1;
                    q.push(num);
                }
            }
        }
    }
    // in ra kết quả
    cout << mp.size() << el;
    for(auto &i : mp) cout << i.first << ' ';
    cout << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;



void LonggVuz(){
    string s; cin >> s;
    stack<char> l, r;
    for(char &c : s){
        if(c == '<'){
            if(l.empty()) continue;
            char i = l.top(); l.pop();
            r.push(i);
        }else if(c == '>'){
            if(r.empty()) continue;
            char i = r.top(); r.pop();
            l.push(i);
        }else if(c == '-'){
            if(!l.empty()) l.pop();
        }else{
            l.push(c);
        }
    }
    string res = "";
    while(!l.empty()){
        res.pub(l.top()); l.pop();
    }
    reverse(all(res));
    while(!r.empty()){
        res.pub(r.top()); r.pop();
    }
    if(res == "") exit(0);
    cout << res;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

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

#define el '\n'
#define mxn 100005

int n, q, a[mxn], dp[mxn];
stack<int> st;

void solve(){
    cin >> n >> q;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    st.push(n);
    dp[n] = 0;
    for(int i=n-1; i>=1; i--){
        while(!st.empty() and a[st.top()] <= a[i]){
            st.pop();
        }
        if(!st.empty()){
            dp[i] = dp[st.top()] + 1;
        }else dp[i] = 0;
        st.push(i);
    }
    while(q--){
        int x; cin >> x;
        cout << dp[x] << el;
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'

int n;
map<string, int> mp;
int cal(string s){
    int res = 0;
    for(char &c : s){
        res = res * 10 + (c - '0');
        res %= n;
    }return res;
}
 
void solve(){
    cin >> n;
    queue<string> q;
    q.push("6"); mp["6"] = cal("6");
    q.push("8"); mp["8"] = cal("8");
    while(!q.empty()){
        string s = q.front(); q.pop();
        if(s.size() > 200) break;
        if(mp[s] == 0){
            cout << s; return;
        }
        string x = s + "6";
        if(mp[x] == 0){
            mp[x] = cal(x);
            q.push(x);
        }
        string y = "8" + s;
        if(mp[y] == 0){
            mp[y] = cal(y);
            q.push(y);
        }
    }
    cout << -1;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

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

#define el '\n'

int n, m, a[1005][1005], l[1005][1005], r[1005][1005];
 
void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> a[i][j];
            if(a[i][j]){
                a[i][j] = a[i - 1][j] + 1;
            }
        }
    }
    for(int i=1; i<=n; i++){
        stack<int> st1;
        st1.push(1);
        l[i][1] = 0;
        for(int j=2; j<=m;j++){
            while(!st1.empty() && a[i][j] <= a[i][st1.top()]){
                st1.pop();
            }if(st1.empty()){
                l[i][j] = 0;
            }else l[i][j] = st1.top();
            st1.push(j);
        }
        stack<int> st2;
        st2.push(m);
        r[i][m] = m + 1;
        for(int j=m-1; j>=1; j--){
            while(!st2.empty() && a[i][j] <= a[i][st2.top()]){
                st2.pop();
            }if(st2.empty()){
                r[i][j] = m + 1;
            }else r[i][j] = st2.top();
            st2.push(j);
        }
    }
    int x = 0, y = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            int left = l[i][j] + 1;
            int right = r[i][j] - 1;
            int len = right - left + 1;
            if(a[i][j] * len > x * y){
                x = min(a[i][j], len);
                y = max(a[i][j], len);
            }else if(a[i][j] * len == x * y and abs(a[i][j] - len) < y - x){
                x = min(a[i][j], len);
                y = max(a[i][j], len);
            }
        }
    }
    cout << x << ' ' << y << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, l, r, a[mxn], pf[mxn];

void LonggVuz(){
    cin >> n >> l >> r;
    fo(i, 1, n) cin >> a[i];
    int res = -oo, id = 1;
    deque<int> q;
    q.push_back(0);
    fo(i, 1, n){
        while(!q.empty() and i - q.front() > r) q.pop_front();
        if(i - l >= 1){
            while(!q.empty() and pf[i - l] < pf[q.back()]) q.pop_back();
            q.push_back(i - l);
        }
        pf[i] = pf[i - 1] + a[i];
        if(!q.empty() and i - q.front() >= l){
            // cout << i << ' ' << q.front(), el;
            res = max(res, pf[i] - pf[q.front()]);
        }
    }
    cout << res;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;



void LonggVuz(){
    string s; cin >> s;
    int n = len(s), id = 0;
    while(id < n and s[id] != '*') ++id;
    int res = 0;
    stack<int> st;
    fo(i, 0, n - 1) if(i != id){
        if(s[i] == '('){
            st.push(i);
        }else{
            if(st.empty()) continue;
            if(st.top() < id and id < i){
                ++res;
            }
            st.pop();
        }
    }
    cout << res;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

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

#ifdef LOCAL
#include<LonggVuz.h>
#else
#define debug(...)
#endif

#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define float double
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

vec<int> base; int bs = 167;

void pre(int n){
    base.resize(n + 5, 1);
    fo(i, 1, n) base[i] = base[i - 1] * bs % mod;
}

struct Hash{
    vec<int> h;
    Hash(string &str){
        int n = len(str);
        str.insert(begin(str), ' ');
        h.resize(n + 5);
        fo(i, 1, n) h[i] = (h[i - 1] * bs + str[i] - 'a' + 1) % mod;
    }
    int get(int l, int r){
        return (h[r] - h[l - 1] * base[r - l + 1] % mod + mod) % mod;
    }
};

void LonggVuz(){
    string a; cin >> a;
    int k; cin >> k;
    int n = len(a);
    Hash h(a);
    set<int> s;
    fo(i, 1, n){
        stack<int> st;
        int level = 0;
        fo(j, i, n){
            if(a[j] == '('){
                st.push(len(st) + 1);
            }else{
                if(st.empty()) break;;
                level = max(level, st.top());
                st.pop();
            }
            if(level > k) break;
            if(level == k and st.empty()){
                // debug(i, j, h.get(i, j));
                s.insert(h.get(i, j));
            }
        }
    }
    cout << len(s);
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    pre(1e3);
    signed orz = 1; if(1) cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << clock() << "ms\n";
}