akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<cmath>
#include<math.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<complex>
#include<queue>
#include<set>
#include<utility>
#include<iomanip>
#include<limits>
#include<thread>
#include<map>
#include<stack>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<tuple>

using namespace std;

template <class... A>
void prints() { cout << "\n"; }
template <class... A>
void prints_rest() { cout << "\n"; }
template <class T, class... A>
void prints_rest(const T &first, const A &... rest) { cout << " " << first; prints_rest(rest...); }
template <class T, class... A>
void prints(const T &first, const A &... rest) { cout << first; prints_rest(rest...); }

#define rep(i,n) for(int i=0; i<n; i++)
#define rep1(i,n) for(int i=1; i<n+1; i++)
#define repr(i,n) for(int i=n-1; i>=0; i--)
#define repr1(i,n) for(int i=n; i>0; i--)
#define souatari rep1(i,n-1)rep(j,i)
#define souatari1 for(int i=2; i<n+1; i++)rep1(j,i-1)
#define mp make_pair
#define F first
#define S second
#define elif else if

typedef long long ll;
typedef vector<int>  vi;
typedef vector<vi>  vvi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double D;


const ll llinf =  numeric_limits<ll>::max();
const ll _llinf = numeric_limits<ll>::lowest();
const int inf = numeric_limits<int>::max();
const int _inf = numeric_limits<int>::lowest();
const double dinf = numeric_limits<double>::infinity();
const ll MOD = 1000000007;





int main(){ 
  cin.tie(0); ios::sync_with_stdio(false);
  int n;
  string s;

  cin >> n;
  cin >> s;
  int ans = 0;

  rep1(i,n-1){
    int lp = 0;
    int rp = i;
    int tmpcnt = 0;
    bool flag = false;
    rep(p,n-i){
      if (flag && s[lp] != s[rp]){
        if(i < tmpcnt){
          ans = max(ans,i);
          flag = false;
          tmpcnt = 0;
        }
        else{
          ans = max(ans,tmpcnt);
          flag = false;
          tmpcnt = 0;
        }
      }
      elif(s[lp] == s[rp]){
        tmpcnt++;
        flag = true;
      }
      lp++;
      rp++;
    }
    if (flag){
        if(i < tmpcnt){
          ans = max(ans,i);
          flag = false;
          tmpcnt = 0;
        }
        else{
          ans = max(ans,tmpcnt);
          flag = false;
          tmpcnt = 0;
        }
      }

  }

  cout << ans << endl;


  return 0;

}


Measured memory_bytes: 384
while True:
    T,D,L=map(int,input().split())
    if T==0 and D==0 and L==0:
        break
    rem,ans=0,0
    for _ in [0]*T:
        x=int(input())
        if x >= L:
            rem=D
        if rem:
            ans+=1
            rem-=1
    if ans:
        ans-=1
    print(ans)

Measured memory_bytes: 8764
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cassert>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int dx[] = {0, 0, 1, -1};
constexpr int dy[] = {1, -1, 0, 0};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, dp[112345];

    cin >> n;

    dp[0] = 0;
    dp[1] = 1;
    int six = 6;
    int nine = 9;
    for (int i = 2; i <= n; i++)
    {
        if (six * 6 <= i)
            six *= 6;
        if (nine * 9 <= i)
            nine *= 9;

        dp[i] = dp[i - 1] + 1;

        if (six <= i)
            dp[i] = min(dp[i], dp[i - six] + 1);

        if (nine <= i)
            dp[i] = min(dp[i], dp[i - nine] + 1);
    }

    cout << dp[n] << endl;

    return 0;
}

Measured memory_bytes: 640
n = int(input())
x = []
y = []
h = []
for i in range(n):
    a,b,c = map(int, input().split())
    x.append(a)
    y.append(b)
    h.append(c)
    
index = h.index(max(h))
for cx in range(101):
    for cy in range(101):
        H = h[index] + abs(x[index] - cx) + abs(y[index] - cy)
        flag = True
        for i in range(n):
            if h[i] > 0:
                if H != (h[i] + abs(x[i] - cx) + abs(y[i] - cy)):
                    flag = False
            if h[i] == 0:
                if (H -  abs(x[i] - cx) - abs(y[i] - cy)) > 0:
                    flag = False
        if flag:
            print(cx,cy,H)

Measured memory_bytes: 3064
#include "bits/stdc++.h"

using namespace std;

using LL = long long int;
using LD = long double;

using pii = pair<int, int>;
using pll = pair<LL, LL>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<LL>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;

const int INF = (1 << 30) - 1;
const LL INF64 = ((LL)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, 1, 0, -1 };

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
LL gcd(LL x, LL y) { return y ? gcd(y, x % y) : x; }

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	vi a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());

	cout << a[n - 1] - a[0] << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>
#include<queue>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

template <class T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
	for (const auto& e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& st) {
	for (const auto& e : st) os << e << " ";
	return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const map<T1, T2>& mp) {
	for (const auto& e : mp) os << e << " ";
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T&& h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head&& h, Tail&&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N;
	cin >> N;

	vector<Int> a(N);
	for (Int i = 0; i < N; i++) {
		cin >> a[i];
	}

	vector<vector<Int>> dp(N+1, vector<Int>(N+1,INF));//dp[i][j]:区間[i,j)を合体させるのに必要な最小コスト
	for (Int i = 0; i < N; i++) {
		dp[i][i + 1] = 0;
	}

	vector<Int> s(N + 1);//累積和
	for (Int i = 0; i < N; i++) {
		s[i + 1] = s[i] + a[i];
	}

	//dp
	for (Int len = 2; len <= N; len++) {
		for (Int i = 0; i+len <= N; i++) {
			Int j = i + len;
			for (Int k = i+1; k < j; k++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + s[j] - s[i]);
				//dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
		DMP(dp);
	}

	cout << dp[0][N] << "\n";
}


Measured memory_bytes: 1536
//Himanshu Shukla
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define file_input
//#define multitest
//#define measure_time
#define ll long long
#define v32 vector<int>
#define v64 vector<ll>
#define s32 set<int>
#define s64 set<ll>
#define graph vector<v32>
#define p32 pair<int, int>
#define p64 pair<ll, ll>
#define sz(v) (ll)(v).size()
#define fi first
#define se second
#define ln '\n'
#define debug(x) cerr << (#x) << ": " << (x) << ln
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll add(ll a, ll b, ll m) { return (((a % m + b % m) % m + m) % m); }
inline ll mul(ll a, ll b, ll m) { return (((a % m * b % m) % m + m) % m); }
const double EPS = 1e-6;
const ll MOD = 1e9 + 7;
template <typename T, typename U>
ostream &operator<<(ostream &out, const pair<T, U> &p)
{
	out << '[' << p.fi << ", " << p.se << ']';
	return out;
}
template <template <typename, typename...> class ContainerType, typename ValueType, typename... Args>
void print_container(const ContainerType<ValueType, Args...> &c)
{
	cout << "{ ";
	for (const auto &v : c)
		cout << v << ' ';
	cout << '}' << ln;
}

ll dp[20][10][2];
ll go(int i, int prev, int flag, v32 &dig)
{
	if (i >= sz(dig))
		return 1;
	if (dp[i][prev][flag] != -1)
		return dp[i][prev][flag];
	ll ans = 0;
	if (flag)
	{
		if (abs(dig[i] - prev) <= 1)
			ans += go(i + 1, dig[i], 1, dig);
		for (int j = 0; j < dig[i]; j++)
			if (abs(j - prev) <= 1)
				ans += go(i + 1, j, 0, dig);
	}
	else
	{
		for (int j = 0; j < 10; j++)
			if (abs(prev - j) <= 1)
				ans += go(i + 1, j, 0, dig);
	}
	return dp[i][prev][flag] = ans;
}

ll getCount(ll x)
{
	v32 dig;
	while (x)
	{
		dig.push_back(x % 10);
		x /= 10;
	}
	reverse(dig.begin(), dig.end());
	memset(dp, -1, sizeof(dp));
	int n = dig.size();
	ll cnt = go(1, dig[0], 1, dig);
	for (int j = 1; j < dig[0]; j++)
		cnt += go(1, j, 0, dig);
	for (int i = 2; i <= n; i++)
		for (int j = 1; j < 10; j++)
		{
			cnt += go(i, j, 0, dig);
		}
	return cnt;
}

bool check(ll x, ll k)
{
	return (getCount(x) >= k);
}

void solve()
{
	ll k;
	cin >> k;
	ll lo = 0, hi = 1e18, ans = 0;
	while (hi - lo > 1)
	{
		ll mid = (lo + hi) / 2;
		if (check(mid, k))
			hi = ans = mid;
		else
			lo = mid;
	}
	cout << ans << ln;
	return;
}

int main()
{
	FASTIO;
#ifdef file_input
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	clock_t start, stop;
	int t = 1;
#ifdef multitest
	cin >> t;
#endif
#ifdef measure_time
	start = clock();
#endif
	for (int tc = 1; tc < t + 1; tc++)
		solve();
#ifdef measure_time
	stop = clock();
	cerr << "Time :" << fixed << setprecision(5) << double(stop - start) / double(CLOCKS_PER_SEC) << "s" << ln;
#endif
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    HashMap<Integer, List<Integer>> routes = new HashMap<Integer, List<Integer>>();
    
    for (int i=0; i<h; i++) {
      String row = sc.next();
      for (int j=0; j<w; j++) {
        char c = row.charAt(j);
        if (c=='.') {
          List<Integer> tmp = new ArrayList<Integer>();
          routes.put(i*w+j, tmp);
          
          if (i!=0) {
            if (routes.containsKey((i-1)*w+j)) {
              tmp.add((i-1)*w+j);
              routes.get((i-1)*w+j).add(i*w+j);
            }
          }
          
          if (j!=0) {
            if (routes.containsKey(i*w+j-1)) {
              tmp.add(i*w+j-1);
              routes.get(i*w+j-1).add(i*w+j);
            }
          }
        }
      }
    }
    
    int max = 1;
    if (routes.size()==h*w) {
      max = h + w -2;
    }
    else {
    for (int i=0; i<h*w; i++) {
      for (int j=i+1; j<h*w; j++) {
        if (!routes.containsKey(i)) {
          continue;
        }
        if (!routes.containsKey(j)) {
          continue;
        }
        HashMap<Integer, Integer> already = new HashMap<Integer,Integer>();
        Deque<Integer> queue = new ArrayDeque<Integer>();
        
        queue.offer(i);
        already.put(i, 0);
        while(!queue.isEmpty()) {
          int current = queue.poll();
          List<Integer> way = routes.get(current);
          for (Integer k : way) {
            if (already.containsKey(k)) {
              continue;
            }
            queue.offer(k);
            already.put(k, already.get(current)+1);
          }
        }
        
        if (max<already.get(j)) {
          max = already.get(j);
        }
      }
    }  
    }
    
    
    
    

    System.out.println(max);
  }
}

Measured memory_bytes: 231996
// https://abc115.contest.atcoder.jp/tasks/abc115_c
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int number_of_trees,number_of_decorated;
    vector<int> treeRow;
    cin>>number_of_trees>>number_of_decorated;
    for(int i=0;i<number_of_trees;i++)
    {
        int this_tree;
        cin>>this_tree;
        treeRow.push_back(this_tree);
    }
    sort(treeRow.begin(),treeRow.end());
    
    int min=INT_MAX;
    for(int i=0;i<number_of_trees-number_of_decorated+1;i++)
    {
        int this_difference=treeRow[number_of_decorated+i-1]-treeRow[i];
        min=(this_difference<min)?this_difference:min;
    }
    cout<<min<<endl;
    return 0;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>

using namespace std;
using llong = long long;
using P = pair<llong, llong>;

#define BE(x) x.begin(), x.end()

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

int main(){
	llong N, A, B;
	string S;

	cin >> N >> A >> B >> S;
	int decide = 0, b = 0;
	for(int i = 0; i < (int)S.size(); i++){
		string ret = "No";
		if(S[i] == 'a' && decide < A+B)
			decide++, ret = "Yes";
		else if(S[i] == 'b' && b < B && decide < A+B)
			decide++, b++, ret = "Yes";
		cout << ret << endl;
	}

	return 0;
}

Measured memory_bytes: 896
using System;
using System.Collections;
using System.Collections.Generic;

namespace 練習問題
{
    class Program {
        static void Main(string[] args) {
            debug Debug = new debug();
            string[] input = Console.ReadLine().Split(' ');
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            int c = int.Parse(input[2]);
            int localsave = 0;
            localsave = a;
            a = b;
            b = localsave;
            localsave = c;
            c = a;
            a = localsave;
            Console.WriteLine(a + " " + b + " " + c);
        }

        static void bubble_sort(List<List<int>> a) {
            int count=0;
            for (int i = 0; i < a.Count; i++) {
                for (int j = 0; j < a.Count-i-1; j++) {
                    // if (a[j] == a[a.Count - 1]){
                    //     continue;
                    // }
                    count++;
                    if (a[j][1] > a[j+1][1]){
                        int localsave = 0;
                        localsave = a[j+1][1];
                        a[j+1][1] = a[j][1];
                        a[j][1] = localsave;
                        localsave = a[j][0];
                        a[j][0] = a[j+1][0];
                        a[j+1][0] = localsave;
                    }
                }
                //debug(a,"途中" + i);
            }
            // debug(a,"result");
            //Console.WriteLine("回数"+count);
            for (int i = 0; i < a.Count; i++)
            {
                Console.WriteLine(a[i][0]+" "+a[i][1]);
            }
        }
        /* 標準入力と標準出力が使えるかのチェック
        static void echo() {
            string echotest = Console.ReadLine();
            Console.WriteLine(echotest);
        }

        static void HelloWorld(){
            Console.WriteLine("Hello World!");
        }
        */
    }

    public class debug{
        public void Log(string str){
            Console.WriteLine(str);
        }
        public void Log(int str){
            Console.WriteLine(str);
        }
        public void Log(object obj){
            Console.WriteLine(obj);
        }

        public void Log(int[] arr){
            Console.WriteLine(string.Join(",", arr));
        }
        public void Log(string[] arr){
            Console.WriteLine(string.Join(",", arr));
        }
        public void Log(List<int> arr){
            string shuturyoku = "";
            for (int i = 0; i < arr.Count; i++) {
                shuturyoku += arr[i] + " ";
            }
            Console.WriteLine(shuturyoku.TrimEnd(' '));
        }
    }
}

Measured memory_bytes: 13140
#include <iostream>
using namespace std;
int main(){
	long long l,r;
	cin>>l>>r;
	long long min=2100000000;	
	for(long long i=l;i<=r;i++){
		for(long long j=i+1;j<=r;j++){
			if(i%2019==0||j%2019==0){
				cout<<"0";
				return 0;
			}
			if((i%2019)*(j%2019)%2019<min)min=((i%2019)*(j%2019))%2019;
		}
	}
	cout<<min;
}

Measured memory_bytes: 256
// Copyright lzt
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<ctime>
using namespace std;
typedef long long ll;
typedef std::pair<int, int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair<long long, long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i, j, k)  for (register int i = (int)(j); i <= (int)(k); i++)
#define rrep(i, j, k) for (register int i = (int)(j); i >= (int)(k); i--)
#define Debug(...) fprintf(stderr, __VA_ARGS__)

inline ll read() {
  ll x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch <= '9' && ch >= '0') {
    x = 10 * x + ch - '0';
    ch = getchar();
  }
  return x * f;
}

const int maxn = 100100;
int n;
int a[maxn], b[maxn], c[maxn];
int f[maxn][3];

void work() {
  n = read();
  rep(i, 1, n) a[i] = read(), b[i] = read(), c[i] = read();
  rep(i, 1, n) {
    f[i][0] = max(f[i - 1][1], f[i - 1][2]) + a[i];
    f[i][1] = max(f[i - 1][0], f[i - 1][2]) + b[i];
    f[i][2] = max(f[i - 1][0], f[i - 1][1]) + c[i];
  }
  printf("%d\n", max(f[n][0], max(f[n][1], f[n][2])));
}

int main() {
  #ifdef LZT
    freopen("in", "r", stdin);
  #endif

  work();

  #ifdef LZT
    Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
  #endif
}


Measured memory_bytes: 2560
import qualified Data.ByteString.Char8 as BS
import Data.List

main = do
  [n, x] <- unfoldr (BS.readInt . BS.dropWhile (== ' ')) <$> BS.getLine
  as <- sort <$> unfoldr (BS.readInt . BS.dropWhile (== ' ')) <$> BS.getLine
  print $ solve x as

solve x [a] = if x == a then 1 else 0
solve x (a : as)
  | x == a = 1
  | x < a = 0
  | otherwise = 1 + solve (x - a) as

Measured memory_bytes: 3764
N,L = map(int, input().split())

t = [0]*N

S = int(N/2*(N+2*L-1))

m = 100
for i in range(N):
    t[i] = L + i
    
    if abs(t[i]) < abs(m):
        m = t[i]
print(S-m)        

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n , T ;
  cin >> n >> T ;
  int ans = 0 ;
  int stop = 0;
  for(int i=0; i<n; i++){
    int x ;
    cin >> x ;
    
    if(stop < x)
      ans += T;
    else 
      ans += T+x-stop ;
    stop = x + T ;
  }
  
  cout << ans ;
    
}


Measured memory_bytes: 256
from collections import Counter
n=int(input())
v=list(map(int,input().split()))
a=Counter(v[::2]).most_common()
b=Counter(v[1::2]).most_common()
a.append([0,0])
b.append([0,0])
if a[0][0]!=b[0][0]:
    print(n-(a[0][1]+b[0][1]))
else:
    print(min((n-(a[1][1]+b[0][1])),n-(a[0][1]+b[1][1])))

Measured memory_bytes: 20700
#include<bits/stdc++.h>
#define PI 3.141592653589
#define ll long long
using namespace std;

int main(){
  int n;
  cin >> n;
  
  int a[n];
  for(int i=0; i<n; ++i){
    cin >> a[i];
  }
  for(int i=0; i<n; ++i){
    if(a[i]%2 == 0 && a[i]%3 != 0 && a[i]%5 != 0){
      cout << "DENIED";
      return 0;
    }
  }
  
  cout << "APPROVED";
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int D,N,ans,i;
	
	scanf("%d %d",&D,&N);
	if(N!=100){
		if(D==0)
		ans=N;
		else if(D==1)
			ans=N*100;
		else if(D==2)
			ans=N*10000;
	}
	else
		if(D==0)
		ans=101;
		else if(D==1)
			ans=101*100;
		else if(D==2)
			ans=101*10000;
		
	printf("%d\n",ans);
	
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

bool is_prime(int num);
int cnt(int num, int n);

int prime_cnt[110];

int main(){
    int N;
    cin >> N;
    if(N == 1){
        cout << 0 << endl;
        return 0;
    }
    
    vector<int> prime_number;
    for(int i = 2; i <= N; ++i){
        if(is_prime(i))    prime_number.push_back(i);
    }
    
    for(int i = 2; i <= N; ++i){
        int temp = i;
        int index = 0;
        while(temp > 1){
            while(temp % prime_number[index] == 0){
                temp /= prime_number[index];
                prime_cnt[prime_number[index]]++;
            }
            index++;
        }
    }
    
    
    // (4, 4, 2), (14, 4), (24, 2), (74)
    int t1 = cnt(2, N);
    int t2 = cnt(4, N);
    int res = cnt(74, N) + cnt(24, N) * (t1 - 1) + cnt(14, N) * (t2 - 1) + (t2 * (t2 - 1) / 2) * (t1 - 2);
    
    cout << res << endl;
}

bool is_prime(int num){
    if(num <= 3){
        return num > 1;
    }
    else if(num % 2 == 0 || num % 3 == 0){
        return false;
    }
    else{
        for(int i = 5; i * i <= num; i += 6){
            if(num % i == 0 || num % (i + 2) == 0){
                return false;
            }
        }
    }
    
    return true;
}

int cnt(int num, int n){
    int temp = 0;
    for(int i = 0; i <= n; ++i){
        if(prime_cnt[i] >= num)     temp++;
    }
    
    return temp;
}

Measured memory_bytes: 256
//
//  main.cpp
//  C - Poll
//
//  Created by Hashizo on 2020/02/16.
//  Copyright © 2020 Hashizo. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <regex>
#include <cmath>

using namespace std;
 
#undef LONG_MAX
#undef LONG_MIN
 
#define LONG_MAX    9223372036854775807
#define LONG_MIN    (-LONG_MAX  -1)
 
#define ll long long
 
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
 
#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())

typedef struct {
    ll cnt;
    string str;
}POLL;


int main(int argc, const char * argv[]) {

	ll maxCnt = 1;

	string s;

	ll n;
	cin >> n;
	
	vector<string> point(n);

	REP(i, n) {
		cin >> point[i];
	}
	
	SORT(point);

	vector<POLL> pp;
	
	ll cnt = 1;
	string wk = point[0];
	FOR(i, 1, n) {
		if (wk == point[i]) {
			cnt++;
		}
		else {
			POLL p;
			p.cnt = cnt;
			p.str = wk;
			pp.push_back(p);
			if(cnt >  maxCnt) {
				maxCnt = cnt;
			}
			wk = point[i];
			cnt = 1;
		}
	}
	POLL p;
	p.cnt = cnt;
	p.str = wk;
	pp.push_back(p);
	if(cnt >  maxCnt) {
		maxCnt = cnt;
	}

	
	
	
	
	vector<string> maxstring;
	
	REP(i, pp.size()) {
		if (pp[i].cnt ==  maxCnt) {
			maxstring.push_back(pp[i].str);
		}
	}

	REP(i, maxstring.size()) {
		cout << maxstring[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 20976
//g++でビルド

#include "bits/stdc++.h"

using namespace std;


int main(){
    int d, g;
    cin >> d >> g;
    int p[d];
    int c[d];
    for(int i = 0; i < d; i++){
        cin >> p[i] >> c[i];
    }

    int result = 1000000000;
    for(int bit = 0; bit < (1<<d); bit++){
        int point = 0;
        int num = 0;
        for(int i = 0; i < d; i++){
            if(bit & (1<<i)){
                point += (100 * (i+1) * p[i] + c[i]);
                num += p[i];
            }
        }
        if(point >= g){
            if(result > num){
                result = num;
            }
        }else{
            int rest = g - point;
            for(int i = d - 1; i >= 0; i--){
                if(bit & (1<<i)){
                
                }else{
                    int restnum = (rest + 100 * i) / (100 * (i+1));
                    if(restnum >= p[i]){
                        num = -1;
                        break;
                    }else{
                        num += restnum;
                        break;
                    }
                }
            }
            if(num != -1 && result > num){
                result = num;
            }
        }
    }

    cout << result << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <functional>
#include <chrono>
#include <cstring>
#include <bits/stdc++.h>

using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MM_PI		3.14159265358979323846

typedef vector<lint> vl;
typedef pair<lint,lint> pll;

#define mpr make_pair

int main()
{
    ios_base::sync_with_stdio(0);    cin.tie(NULL);    cout.tie(NULL);

    int a,b,h,m; cin>>a>>b>>h>>m;

    double dh = h + double(m)/60.0;

    typedef double db;

    db ha = dh/12 * 2 * MM_PI;
    db ma = double(m)/60.0 * 2 * MM_PI;

    db x1 = a*sin(ha); db y1 = a*cos(ha);

    db x2 = b*sin(ma); db y2 = b*cos(ma);
    cout.precision(19);
    cout<<sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));

}


Measured memory_bytes: 4140
#include<bits/stdc++.h>							
typedef long long ll;
#define pb push_back
#define mod 1000000007ll
const ll maxn = 9e18;
using namespace std;
const ll maxsize = 100000009;


void solve() {
	int n;
	cin >> n;
	vector<int> a(n), b(n), a_c;
	for(int i = 0; i < n; ++i) cin >> a[i];
	for(int i = 0; i < n; ++i) cin >> b[i]; 
	a_c = a;
	sort(a.begin(), a.end());
	ll cnt = 0, cnt2 = 0;
	bool flag = true, flag2 = true;
	do {
		if(a == a_c) flag = false;
		if(a == b) flag2 = false;
		if(flag) cnt++;
		if(flag2) cnt2++;
		} while(next_permutation(a.begin(), a.end()));
		cout << abs(cnt - cnt2) << endl;
}


int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout.precision(35);
	solve();
	return 0;
}
 
 
 



Measured memory_bytes: 3636
#include <stdlib.h>
#include <iostream>
#include <string>
#include <ios>     // std::left, std::right
#include <vector> // std::setw(int), std::setfill(char)
using namespace std;

int main()
{

	int a, b;
	cin >> a >> b;
	int max;

	
	max = a + b;
	if (a - b > max)
	{
		max = a - b;
	}
	if (a * b > max)
	{
		max = a *b;
	}

	cout << max << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    swap(a,b);
    swap(a,c);
    cout<<a<<" "<<b<<" "<<c;
}

Measured memory_bytes: 256
n, w = map(int, input().split())

wei = []
val = []

for i in range(n):
    x, y = map(int, input().split())
    wei.append(x)
    val.append(y)

dp = [[0 for i in range(w + 1)] for j in range(n + 1)]

for i in range(n):
    for weight in range(w + 1):
        if wei[i] < weight + 1:
            dp[i + 1][weight] = max(dp[i][weight], dp[i][weight - wei[i]] + val[i])

        else:
            dp[i + 1][weight] = dp[i][weight]
print(dp[n][w])


Measured memory_bytes: 171528
//This code was made by Chinese_zjc_.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#define int long long
#define INF 0x3fffffffffffffff
using namespace std;
string s;
int ans,now,n,p[1000003];
signed main()
{
	cin>>s;
	n=s.length();
	for(int i=0;i<n>>1;++i)
	{
		swap(s[i],s[n-i-1]);
	}
	s=' '+s;
	for(int i=1;i<=n;++i)
	{
		p[i]=s[i]-'0';
	}
	for(int i=1;i<=n+1;++i)
	{
		if(p[i]==10)
		{
			p[i]=0;
			++p[i+1];
		}
		if(p[i]>=6||(p[i]==5&&p[i+1]>=5))
		{
			ans+=10-p[i];
			++p[i+1];
			continue;
		}
		if(p[i]<=5)
		{
			ans+=p[i];
		}
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 9136
#include <algorithm>
// INT_MAXのためにclimits追加した
#include <climits>
#include <iostream>
#include <list>
#include <vector>
using namespace std;
typedef long long li;
#define MOD 1000000007
#define rep(i, n) for (int i = 0; i < (n); i++)
#define df 0
template <class T>
void print(const T& t) {
    cout << t << "\n";
}
template <class T, class... Ts>
void print(const T& t, const Ts&... ts) {
    cout << t;
    if (sizeof...(ts)) cout << " ";
    print(ts...);
}
//コード整形がバグるからostreamとかのやつを消した

void dfs(vector<vector<int>>& adj, vector<int>& ans, const vector<li>& a, int parent = -1,
         int v = 0) {
    // INT_MAXで全部初期化
    static vector<li> lis(a.size(), INT_MAX);

    auto itr = lower_bound(lis.begin(), lis.end(), a[v]);
    int flag = (itr != lis.end());
    li memo;
    if (flag) {
        memo = *itr;
        *itr = a[v];
    } else
        lis.push_back(a[v]);

    // INT_MAXのない部分の長さがLISの長さ
    ans[v] = lower_bound(lis.begin(), lis.end(), INT_MAX) - lis.begin();
    for (int x : adj[v]) {
        if (x == parent) continue;
        dfs(adj, ans, a, v, x);
    }

    if (flag)
        *itr = memo;
    else
        lis.pop_back();
}

int main() {
    int n;
    cin >> n;
    vector<li> a(n);
    rep(i, n) cin >> a[i];
    vector<vector<int>> adj(n);
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> ans(n, -1);
    dfs(adj, ans, a);

    rep(i, n) print(ans[i]);
}

Measured memory_bytes: 35308
#include <stdio.h>

#define N 2000001
#define E 10000

int A[N],B[N],C[N],n;

void CountingSort(int);
void Print(int *);

main(){
  
  int i,k=0;
  n=0;
  
  scanf("%d",&n);
  
  if(N < n || n < 0) return 0;
  
  for(i=1;i <= n;i++){
    scanf("%d",&A[i]);
    
    if(E < A[i]|| A[i] < 0) return 0;
    
    if(k < A[i]) k=A[i]+1;
  }
  
  CountingSort(k);
  
  Print(B);
  
  return 0;
}

void CountingSort(int k){
  int i,j;
  
  for(i = 0;i <= k;i++) C[i] = 0;
  
  for(j = 1;j <= n;j++) C[A[j]]++;
  
  for(i = 1;i <= k;i++) C[i] = C[i]+C[i-1];
  
  for(j = n; j > 0;j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }
}

void Print(int *B){
  int i;
  
  for(i=1;i <= n;i++){
    if(i == n) printf("%d",B[i]);
    else printf("%d ",B[i]);
  }
  printf("\n");
}

Measured memory_bytes: 17896
import java.util.*;
public class Main {
    public static void main(String[] args ){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int s = sc.nextInt();
        int count = 0;
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j <= k; j++) {
                int com = s - (i+j);
                if (com >=0 && k >= com) count++;
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 35684
import java.util.*

fun main(args: Array<String>) {
  val sc = Scanner(System.`in`)
  val n = sc.nextInt()
  val a = (1..n).map { sc.nextInt() }

  val min = a.min()!!
  val max = a.max()!!

  val list = mutableListOf<Long>()
  for (i in min..max) {
    var sum = 0L
    for (ai in a) {
      val tmp = (i - ai) * (i - ai)
      sum += tmp.toLong()
    }
    list.add(sum)
  }

  println(list.min())

}


Measured memory_bytes: 37756
#include<iostream>
#include<string>
#include<cctype>

using namespace std;

string toUpper(string s){
    string t=s;
    for (int i=0;i<s.size();i++){
        t[i]=toupper(s[i]);
    }
    return t;
}

int main(){
    string target,source;
    
    cin>>target;
    target=toUpper(target);
    
    int cnt=0;
    
    while(1){
        cin>>source;
        if (source=="END_OF_TEXT") break;
        source=toUpper(source);
        if (target==source) cnt++;
    }
    
    cout<<cnt<<endl;
    
    return 0;
    
}


Measured memory_bytes: 3168
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    # f(A,B)=f(0,B)^f(0,A-1)
    # f(0,x)はmod 4の値で場合分けでき、
    # x=0: f(0,x)=x
    # x=1: f(0,x)=1
    # x=2: f(0,x)=x+1
    # x=3: f(0,x)=0

    A,B=map(int,input().split())

    if(B%4==0):
        SB=B
    elif(B%4==1):
        SB=1
    elif(B%4==2):
        SB=B+1
    else:
        SB=0

    A-=1
    if(A<0):
        SA=0
    elif(A%4==0):
        SA=A
    elif(A%4==1):
        SA=1
    elif(A%4==2):
        SA=A+1
    else:
        SA=0

    print(SA^SB)
resolve()

Measured memory_bytes: 38256
import sys
n,y = map(int,input().split())
for i in range(n+1):
    for j in range(n-i+1):
        k = n-i-j
        ans = 10000*i+5000*j+1000*k
        if ans == y:
            print('{} {} {}'.format(i,j,k))
            sys.exit()
print('-1 -1 -1')


Measured memory_bytes: 2940
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        if (s.equalsIgnoreCase("SRS")
                || s.equalsIgnoreCase("SSR")
                || s.equalsIgnoreCase("RSS")
                || s.equalsIgnoreCase("RSR")) {
            System.out.println(1);
        }
        else if(!s.contains("R")){
            System.out.println(0);
        }
        else if(s.equalsIgnoreCase("RRR")){
            System.out.println(3);
        }
        else System.out.println(2);
    }
}


Measured memory_bytes: 26984
#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);i++)
#define REAP(i,a,n) for(int i=(a);i<(n);i++)
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define fr first
#define sc second
#define pb push_back
#define All(v) v.begin(),v.end()
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);

    int n,m;
    while(cin >> n >> m,n){
        int h[101]={};
        int t[101]={};
        int s,sum=0;
        REP(i,n){
            cin >> s;
            sum+=s;
            t[s]=1;
        }
        REP(i,m){
            cin >> s;
            sum-=s;
            h[s]=1;
        }
//        cout << sum << endl;
        if(sum%2!=0){
            cout << -1 << endl;
        }else{
            sum/=2;
            sum*=(-1);
            bool flg=0;
            for(int i=0;i<101;i++){
                if((i+sum)>=0&&(i+sum)<101){
                    if(t[i]==1&&h[sum+i]==1){
                        cout << i << " " << sum+i << endl;
                        flg=1;
                        break;
                    }
                }
            }
            if(!flg)cout << -1 << endl;
        }
    }
}



Measured memory_bytes: 3072
#include<bits/stdc++.h>
#define y1 olweradfas
#define y2 qweoisasdk
#define x1 poeriuweor
#define x2 poriewioru
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int MM = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e6 + 10;

int n, m;

void prework(){

}

void read(){

}

int x1, y1, x2, y2;
int x[MAXN], y[MAXN];
int b[MAXN];

const double PI = acos(-1);

#define _cp(a,b) ((a)<(b))

int subseq(int n, int a[]) {
    static int b[MAXN + 1];
	int i, l, r, m, ret = 0;
	//cout << n << endl; fflush(stdout);
    for (i = 0; i < n; b[l] = i++, ret += (l> ret)) {
        for (m = ((l = 1) + (r = ret)) >> 1; l <= r; m = (l + r) >> 1) {
            if (_cp(a[b[m]], a[i])) {
                l = m + 1;
            } else {
                r = m - 1;
            } 
        } 
    }
    return ret;
}

template <typename T>
int LIS(int a[], int n, T cmp){
	static int cnt, len[MAXN];
	len[cnt = 0] = INT_MIN;
	for (int i = 0; i < n; ++i)
		(cmp(len[cnt], a[i]) ? len[++cnt] : *lower_bound(len, len + cnt + 1, a[i], cmp)) = a[i];
	return cnt;
}

void solve(int casi){
	scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
	scanf("%d", &n);
	if (x1 > x2) swap(x1, x2), swap(y1, y2);
	for (int i = 1; i <= n; i++){
		scanf("%d%d", &x[i], &y[i]);
		if (y1 > y2)
			y[i] = y1 - y[i];
	}
	if (y1 > y2) y2 = y1 - y2, y1 = 0;
	vector<PII> a;
	for (int i = 1; i <= n; i++){
		if (x1 <= x[i] && x[i] <= x2 && y1 <= y[i] && y[i] <= y2){
			a.push_back(PII(x[i] - x1, y[i] - y1));
		}
	}
	x2 -= x1, y2 -= y1;
	sort(a.begin(), a.end());
	for (int i = 0; i < a.size(); i++)
		b[i] = a[i].second;
	int ret = LIS(b, a.size(), less<int>());//subseq(a.size(), b);
	//cout << ret << endl;
	if (ret < min(y2, x2) + 1)
		printf("%.15f\n", 100. * (x2 + y2) - (20 - 5 * PI) * ret);
	else
		printf("%.15f\n", 100. * (x2 + y2) - (20 - 5 * PI) * ret + 5 * PI);
}

void printans(){

}


int main(){
//	std::ios::sync_with_stdio(false);
	prework();
	int T = 1;
//	cin>>T;
	for(int i = 1; i <= T; i++){
		read();
		solve(i);
		printans();
	}
	return 0;
}



Measured memory_bytes: 14960
#include<bits/stdc++.h>
using namespace std;


int main() {
    string b; cin >> b;
    string pair;
    if (b == "A") {
        pair = "T";
    } else if (b == "T") {
        pair = "A";
    } else if (b == "C") {
        pair = "G";
    } else {
        pair = "C";
    }

    cout << pair << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	string a,b;
    cin>>a>>b;
    sort(b.begin(),b.end());
    reverse(b.begin(),b.end());
    sort(a.begin(),a.end());
    if(b>a)printf("Yes\n");
    else printf("No\n");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;

    vector<int> l(n);
    for(int i = 0; i < n; i++) cin >> l[i];

    int maxL = *max_element(l.begin(), l.end());
    cout << (maxL < accumulate(l.begin(),l.end(),0)-maxL ? "Yes":"No") << endl;
}



Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	var wtr = bufio.NewWriter(os.Stdout)

	var S string
	fmt.Scan(&S)
	m := map[int32]bool{}
	var ans bool
	for _, v := range S {
		if _, ok := m[v]; ok {
			ans = true
			break
		}
		m[v] = true

	}
	if ans {
		fmt.Fprintln(wtr, "no")
	} else {
		fmt.Fprintln(wtr, "yes")
	}

	_ = wtr.Flush()
}


Measured memory_bytes: 1844
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
using ll = long long;
using P = pair<int, int>;
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<ll> a(N);
    ll tmp = 0;
    rep(i, N) {
        cin >> a[i];
        tmp ^= a[i];
    }

    vector<ll> b(N, 0);
    rep(i, N) {
        b[i] = tmp ^ a[i];
    }

    bool ok = true;
    rep(i, N) {
        if (b[i] != a[i]) {
            ok = false;
        }
    }

    cout << (ok ? "Yes" : "No") << endl;

}


Measured memory_bytes: 1792
import scala.io.StdIn


object Main extends App {
  val Array(n, m)  = StdIn.readLine.split(" ").map(_.toInt)
  var l = 0
  var r = n


  (1 to m).foreach { i =>
    val a  = StdIn.readLine.split(" ").map(_.toInt)
    l = l max a(0)
    r = r min a(1)

  }

  println((r - l + 1) max 0)
}
  



Measured memory_bytes: 43072
#include <bits/stdc++.h>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };


ll dp[1005][1005];

void solve() {
    int q; cin >> q;
    rep(i, q){
        string s, t; cin >> s >> t;
        memset(dp, 0, sizeof(dp));
        // int n = min(s.size(), t.size());
        rep(i, s.size()){
            rep(j, t.size()){
                if(s[i] == t[j]){
                    dp[i+1][j+1] = dp[i][j]+1;
                }else{
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        cout << dp[s.size()][t.size()] << endl;
    }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}



Measured memory_bytes: 15152
#include <bits/stdc++.h>
using namespace std;

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


#define INF 1125899906842624
vector<i64> G[200'000];
vector<i64> A;
vector<i64> dp;
vector<i64> ans;

void dfs(i64 u, i64 prev) {
    auto it = lower_bound(dp.begin(), dp.end(), A[u]);
    i64 oldi = it - dp.begin();
    i64 oldv = *it;
    *it = A[u];
    ans[u] = lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
    ans[u]--;
    for (i64 v : G[u]) {
        if (v == prev) continue;
        dfs(v, u);
    }
    dp[oldi] = oldv;
}

int main() {
    i64 N; cin >> N;
    A.resize(N);
    REP(i, N) cin >> A[i];
    REP(i, N - 1) {
        i64 u, v; cin >> u >> v;
        u--; v--;
        G[u].pb(v);
        G[v].pb(u);
    }

    dp.resize(N + 1);
    fill(dp.begin(), dp.end(), INF);
    dp[0] = -INF;
    ans.resize(N);
    dfs(0, -1);

    REP(i, N) {
        cout << ans[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 30292
#include <bits/stdc++.h>
using namespace std;
int main()
{
  string x;
  cin>>x;
  if(x[0]=='S')
  cout<<"Cloudy";
  else if(x[0]=='C')
  cout<<"Rainy";
  else if(x[0]=='R')
  cout<<"Sunny";
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include <numeric>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999

using namespace std;



int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int dxx[8] = { 0,0,1,1,1,-1,-1,-1 };
int dyy[8] = { 1,-1,0,1,-1,0,1,-1 };


ll m = 1000000007;

ll gcd(ll x, ll y) {
	ll m = max(x, y), n = min(x, y);
	if (m%n == 0)return n;
	else return gcd(m%n, n);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}

ll myPow(ll x, ll n, ll m) {
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return myPow(x * x % m, n / 2, m);
	else
		return x * myPow(x, n - 1, m) % m;
}

using edge = struct { int to; ll cost; };
vector<edge>tree[100010];
ll depth[100010];
int x[100010], y[100010];
int N, Q, K;

void bfs(int K) {
	queue<int> que;
	REP(i, N) {
		depth[i] = INF;
	}
	que.push(K);
	depth[K] = 0;
	while (que.size()) {
		int p = que.front(); que.pop();
		for (auto &e : tree[p]) {
			if (depth[e.to] == INF) {
				que.push(e.to); depth[e.to] = depth[p] + e.cost;
			}
		}
	}
}

int main() {
	cin >> N;
	REP(i, N - 1) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		tree[a].push_back({ b,c });
		tree[b].push_back({ a,c });
	}
	cin >> Q >> K;
	K--;
	bfs(K);
	REP(i, Q) {
		cin >> x[i] >> y[i];
		x[i]--; y[i]--;
	}

	REP(i, Q) {
		cout << depth[x[i]] + depth[y[i]] << endl;
	}
	return 0;
}


Measured memory_bytes: 10752
#include "bits/stdc++.h"

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(aa, (v).size()) { cout << v[aa]; if (aa != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

const int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
const int dy[8] = { 0,1,1,1,0,-1,-1,-1 };


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s; cin >> s;
	int cnt = 0;
	REP(i, s.size())cnt += s[i] - '0';
	cout << cnt << endl;
}


Measured memory_bytes: 256