#include<bits/stdc++.h>
using namespace std; 
#define int long long int
 
 
const int log(int x , int y){
    int count = 0;
    while(x!=0){
        x=x/y;
        count++;
    }
    return count;
}
 
const int ceil(int x , int y){
    if(x%y == 0) return x/y;
    else return (x/y)+1;
}
 
bool isPrime(int n){
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
 
int lcm(int x , int y){
    int alpha = (x*y)/(__gcd(x,y));
    return alpha;
}
// int t[1000007];
 
int myPow(int x, int n) {
    int ans = 1.0;
    for (int i = 0; i < n; i++) {
      ans = ans * x;
    }
    return ans;
}
 
int stringtonum(string s) {
    int num = 0;
    for (char c : s) {
        num = num * 10 + (c - '0');
    }
    return num;
}
 
bool contains_seven(int n) {
    while (n > 0) {
        if (n % 10 == 7) return true;
        n /= 10;
    }
    return false;
}
 
bool check_sqrt(int n){
    int x = sqrt(n);
    if(x*x == n) return true;
    else return false;
}


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

    cout<<n<<endl;
    
   
} 
 
int32_t main(){ 	
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
    int tests; 
    cin>>tests;
    
    for(int i=0;i<tests;i++){
        solve(i);
    }
}

#include<bits/stdc++.h>
using namespace std; 
#define int long long int
 
 
const int log(int x , int y){
    int count = 0;
    while(x!=0){
        x=x/y;
        count++;
    }
    return count;
}
 
const int ceil(int x , int y){
    if(x%y == 0) return x/y;
    else return (x/y)+1;
}
 
bool isPrime(int n){
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
 
int lcm(int x , int y){
    int alpha = (x*y)/(__gcd(x,y));
    return alpha;
}
// int t[1000007];
 
int myPow(int x, int n) {
    int ans = 1.0;
    for (int i = 0; i < n; i++) {
      ans = ans * x;
    }
    return ans;
}
 
int stringtonum(string s) {
    int num = 0;
    for (char c : s) {
        num = num * 10 + (c - '0');
    }
    return num;
}
 
bool contains_seven(int n) {
    while (n > 0) {
        if (n % 10 == 7) return true;
        n /= 10;
    }
    return false;
}
 
bool check_sqrt(int n){
    int x = sqrt(n);
    if(x*x == n) return true;
    else return false;
}


void solve(int tests){
    int n,x;
    cin>>n>>x;

    

    int c[n] , a[n];
    for(int i=0;i<n;i++){
        cin>>c[i];
    }
    for(int i=0;i<n;i++){
        cin>>a[i];
        
    }
    int max_op = n;
    vector<vector<int>> dp(n+1 , vector<int>(max_op+1 , -1 ));
    dp[0][0] = x;

    for(int i=0;i<n;i++){
        for(int op = 0; op<= max_op ; op ++){
            if(dp[i][op] <0 ) continue;
            if(dp[i][op] >= c[i]){
                dp[i+1][op] = max(dp[i+1][op] , dp[i][op] - c[i] + a[i]);
            }
            if(op+1 <= max_op){
                dp[i+1][op+1] = max(dp[i+1][op+1] , dp[i][op] + a[i]);
            }
        }
    }

    int ans = -1;
    for(int i=0;i<=max_op;i++){
        if(dp[n][i] >= 0){
            ans = i;
            break;
        }
    }

    cout<<ans<<endl;
   
} 
 
int32_t main(){ 	
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
    int tests; 
    cin>>tests;
    
    for(int i=0;i<tests;i++){
        solve(i);
    }
}

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


vector<int> sieve_primes(int MAXP) {
    vector<bool> is_composite(MAXP+1,false);
    vector<int> primes;
    for (int i = 2; i <= MAXP; ++i) {
        if (!is_composite[i]) {
            primes.push_back(i);
            if ((int64)i * i <= MAXP) {
                for (int j = i*i; j <= MAXP; j += i)
                    is_composite[j] = true;
            }
        }
    }
    return primes;
}

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

    int t;
    cin >> t;
    vector<int> ns(t);
    int max_n = 0;
    for(int i = 0; i < t; i++){
        cin >> ns[i];
        max_n = max(max_n, ns[i]);
    }

    int limit = floor(sqrt(max_n)) + 1;
    auto primes = sieve_primes(limit);

    for (int n : ns) {
        int64 nn = n;
        int64 sigma = 1;     
        int64 tau   = 1;      
        for (int p : primes) {
            if ((int64)p * p > nn) break;
            if (nn % p == 0) {
                int e = 0;
                int64 p_pow = 1;
                while (nn % p == 0) {
                    nn /= p;
                    e++;
                    p_pow *= p;
                }
          
                int64 sum_p = (p_pow * p - 1) / (p - 1);
                sigma *= sum_p;
                tau   *= (e + 1);
            }
        }
        if (nn > 1) {
          
            sigma *= (1 + nn);
            tau   *= 2;
        }

        
        cout << (sigma - tau) << "\n";
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;

inline int add(int a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

inline int mul(ll a, ll b) {
    return int((a * b) % MOD);
}

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

    int T;
    cin >> T;
    vector<int> ns(T);
    int mx = 0;
    for(int i = 0; i < T; i++){
        cin >> ns[i];
        mx = max(mx, ns[i]);
    }

   
    vector<int> fact(mx+1), der(mx+1);
    fact[0] = 1;
    for(int i = 1; i <= mx; i++){
        fact[i] = mul(fact[i-1], i);
    }

    der[0] = 1;
    if(mx >= 1) der[1] = 0;
    for(int i = 2; i <= mx; i++){
        der[i] = mul(i - 1, add(der[i-1], der[i-2]));
    }

 
    for(int n : ns){
        if(n % 2 == 0){
            cout << 1 << "\n";
        } else {
            cout << mul(fact[n], der[n]) << "\n";
        }
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;


inline int add(int a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}
inline int sub(int a, int b) {
    a -= b;
    if (a < 0) a += MOD;
    return a;
}
inline int mul(ll a, ll b) {
    return int((a * b) % MOD);
}

int modInv(int x) {
    
    int res = 1, power = MOD - 2;
    ll base = x;
    while (power) {
        if (power & 1) res = int((res * base) % MOD);
        base = (base * base) % MOD;
        power >>= 1;
    }
    return res;
}

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

    int T;
    cin >> T;
    vector<int> ns(T);
    vector<vector<int>> allA(T);
    int max_n = 0;
    for(int tc = 0; tc < T; tc++){
        int n;
        cin >> n;
        ns[tc] = n;
        max_n = max(max_n, n);
        allA[tc].resize(n);
        for(int i = 0; i < n; i++){
            cin >> allA[tc][i];
        }
    }

    const int P = 8;
    const int primes[P] = {2,3,5,7,11,13,17,19};

    static int e_exp[21][P];
    for(int v = 1; v <= 20; v++){
        int x = v;
        for(int j = 0; j < P; j++){
            int p = primes[j];
            e_exp[v][j] = 0;
            while(x % p == 0) {
                e_exp[v][j]++;
                x /= p;
            }
        }
    }

    int Mmask = 1<<P;
    static int lsbIdx[1<<P], popc[1<<P];
    for(int m = 1; m < Mmask; m++){
        lsbIdx[m] = __builtin_ctz(m);
        popc[m] = popc[m>>1] + (m&1);
    }
    popc[0] = 0;

    
    int maxInv = 4 * max_n + 5;
    vector<int> inv(maxInv);
    inv[1] = 1;
    for(int i = 2; i < maxInv; i++){
        inv[i] = int((ll)(MOD - MOD/i) * inv[MOD % i] % MOD);
    }

    for(int tc = 0; tc < T; tc++){
        int n = ns[tc];
        auto &A = allA[tc];

        int S[P] = {0};
        vector<int> sum_U(Mmask, 0);
        sum_U[0] = 1;  

        int answer = 0;

        vector<int> Q(Mmask), Aprod(Mmask);

        for(int idx = 0; idx < n; idx++){
            int val = A[idx];
            for(int j = 0; j < P; j++){
                S[j] += e_exp[val][j];
            }
            int CP1[P];
            for(int j = 0; j < P; j++){
                CP1[j] = S[j] + 1;
            }
            int B_fullset = 1;
            for(int j = 0; j < P; j++){
                B_fullset = mul(B_fullset, CP1[j]);
            }

            Q[0] = 1;
            Aprod[0] = 1;
            for(int m = 1; m < Mmask; m++){
                int b = lsbIdx[m];
                int pm = m ^ (1<<b);
                Q[m] = mul(Q[pm], inv[ CP1[b] ]);
                Aprod[m] = mul(Aprod[pm], S[b]);
            }

            ll curSum = 0;
            for(int m = 0; m < Mmask; m++){
                int sign = (popc[m] & 1) ? MOD - 1 : 1; 
                int PU = mul(B_fullset, Q[m]);
             
                ll t = (ll)sum_U[m] * PU % MOD;
                curSum += sign * t;
                if(curSum >= (1LL<<62)) curSum %= MOD; 
            }
            curSum %= MOD;
            answer = int((answer + curSum) % MOD);

           
            for(int m = 0; m < Mmask; m++){
                sum_U[m] = add(sum_U[m], Aprod[m]);
            }
        }

        cout << answer << "\n";
    }

    return 0;
}

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            long n = Long.parseLong(br.readLine().trim());
            sb.append(n).append('\n');
        }
        System.out.print(sb);
    }
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tok = new StringTokenizer(in.readLine());
        int t = Integer.parseInt(tok.nextToken());
        final long NEG_INF = Long.MIN_VALUE / 4;

        while (t-- > 0) {
            tok = new StringTokenizer(in.readLine());
            int n = Integer.parseInt(tok.nextToken());
            long x = Long.parseLong(tok.nextToken());

            int[] c = new int[n];
            int[] a = new int[n];
            tok = new StringTokenizer(in.readLine());
            for (int i = 0; i < n; i++) {
                c[i] = Integer.parseInt(tok.nextToken());
            }
            tok = new StringTokenizer(in.readLine());
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(tok.nextToken());
            }

            long[] dp = new long[n + 1];
            Arrays.fill(dp, NEG_INF);
            dp[0] = x;

            for (int i = 0; i < n; i++) {
                long[] dp2 = new long[n + 1];
                Arrays.fill(dp2, NEG_INF);
                for (int j = 0; j <= i; j++) {
                    if (dp[j] < 0) continue;  
                    if (dp[j] >= c[i]) {
                        dp2[j] = Math.max(dp2[j], dp[j] - c[i] + a[i]);
                    }

                    dp2[j + 1] = Math.max(dp2[j + 1], dp[j] + a[i]);
                }
                dp = dp2;
            }

            int answer = 0;
            while (answer <= n && dp[answer] < 0) {
                answer++;
            }
            System.out.println(answer);
        }
    }
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(r.readLine());
        List<Integer> p = sieve(31623);
        StringBuilder o = new StringBuilder();

        while (t-- > 0) {
            long n = Long.parseLong(r.readLine());
            long x = n, s = 1, c = 1;
            for (int d : p) {
                if ((long) d * d > x) break;
                if (x % d == 0) {
                    int e = 0;
                    while (x % d == 0) {
                        x /= d;
                        e++;
                    }
                    long pw = 1;
                    for (int i = 0; i <= e; i++) pw *= d;
                    long sum = (pw - 1) / (d - 1);
                    s *= sum;
                    c *= (e + 1);
                }
            }
            if (x > 1) {
                s *= (1 + x);
                c *= 2;
            }
            o.append(s - c).append('\n');
        }

        System.out.print(o);
    }

    private static List<Integer> sieve(int n) {
        boolean[] a = new boolean[n + 1];
        List<Integer> l = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (!a[i]) {
                l.add(i);
                if ((long) i * i <= n) {
                    for (int j = i * i; j <= n; j += i) a[j] = true;
                }
            }
        }
        return l;
    }
}

import java.io.*;

public class Main {
    static final int MOD = 998244353;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int[] ns = new int[t];
        int maxOdd = 1;
        for (int i = 0; i < t; i++) {
            ns[i] = Integer.parseInt(br.readLine());
            if ((ns[i] & 1) == 1) {
                maxOdd = Math.max(maxOdd, ns[i]);
            }
        }
        long[] fact = new long[maxOdd + 1];
        fact[0] = 1;
        for (int i = 1; i <= maxOdd; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
        long[] der = new long[maxOdd + 1];
        der[0] = 1;
        if (maxOdd >= 1) der[1] = 0;
        for (int i = 2; i <= maxOdd; i++) {
            der[i] = ( (i - 1L) * (der[i - 1] + der[i - 2]) ) % MOD;
        }
        StringBuilder sb = new StringBuilder();
        for (int n : ns) {
            if ((n & 1) == 0) {
                sb.append(1);
            } else {
                sb.append( fact[n] * der[n] % MOD );
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

import java.io.*;
import java.util.*;

public class Main {
    static final long M = 1_000_000_007L;
    static final int[] P = {2, 3, 5, 7, 11, 13, 17, 19};
    @SuppressWarnings("unchecked")
    static List<int[]>[] L = new ArrayList[21];

    public static void main(String[] args) throws Exception {
        f();
        F s = new F(System.in);
        StringBuilder o = new StringBuilder();
        int t = s.ni();
        while (t-- > 0) {
            int n = s.ni();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = s.ni();
            o.append(sv(a)).append('\n');
        }
        System.out.print(o);
    }

    static long sv(int[] a) {
        int n = a.length;
        long[] p = new long[256];
        long[] mp = new long[256];
        p[0] = 1;
        long ans = (long) n * (n + 1) / 2 % M;

        for (int i = 0; i < n; i++) {
            List<int[]> c = L[a[i]];
            if (c.isEmpty()) continue;

            long[] np = p.clone(), nm = mp.clone(), d = new long[256];

            for (int[] pr : c) {
                int msk = pr[0], w = pr[1];
                for (int j = 0; j < 256; j++) {
                    if ((j & msk) != 0 || (j != 0 && p[j] == 0)) continue;
                    int nmj = j | msk;
                    long pp = (p[j] * w) % M;
                    np[nmj] = (np[nmj] + pp) % M;
                    long min = (j == 0) ? (long) (i + 1) * w % M : (mp[j] * w) % M;
                    nm[nmj] = (nm[nmj] + min) % M;
                    d[nmj] = (d[nmj] + min) % M;
                }
            }

            long rw = n - i;
            for (int j = 1; j < 256; j++) {
                if (d[j] != 0) ans = (ans + d[j] * rw) % M;
            }
            p = np;
            mp = nm;
        }
        return ans;
    }

    static void f() {
        for (int v = 1; v <= 20; v++) {
            int[] e = new int[8];
            int x = v;
            for (int i = 0; i < 8; i++) {
                while (x % P[i] == 0) { e[i]++; x /= P[i]; }
            }
            int m = 0;
            for (int i = 0; i < 8; i++) if (e[i] != 0) m |= 1 << i;
            List<int[]> list = new ArrayList<>();
            for (int s = m; s > 0; s = (s - 1) & m) {
                int w = 1;
                for (int i = 0; i < 8; i++) if ((s & (1 << i)) != 0) w *= e[i];
                list.add(new int[]{s, w});
            }
            L[v] = list;
        }
    }

    private static class F {
        private final byte[] b = new byte[1 << 16];
        private int l = 0, p = 0;
        private final InputStream in;
        F(InputStream in) { this.in = in; }

        int ni() throws IOException {
            int c, s = 1, x = 0;
            while ((c = r()) <= ' ') ;
            if (c == '-') { s = -1; c = r(); }
            do { x = x * 10 + (c - '0'); } while ((c = r()) > ' ');
            return x * s;
        }

        private int r() throws IOException {
            if (p >= l) {
                l = in.read(b);
                p = 0;
                if (l <= 0) return -1;
            }
            return b[p++];
        }
    }
}

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```

```