Template

/**

Normal Template -------------------------------------------------------------51
Chapter-1: Number Theory

Sieve (Prime) ---------------------------------------------------------------92
Sum of all Divisors 1 to N –------------------------------------------------127
nCr-------------------------------------------------------------------------141
nPr-------------------------------------------------------------------------160
GCD-------------------------------------------------------------------------173
LCM-------------------------------------------------------------------------180
Number Factorization--------------------------------------------------------187
Base Conversion-------------------------------------------------------------246
AND, OR, XOR----------------------------------------------------------------300
Is Factorial of any number or not-------------------------------------------790

Chapter-2: Math
Big Mod --------------------------------------------------------------------114
Prefix Sum------------------------------------------------------------------201
Minimum Sub array Sum-------------------------------------------------------543
Maximum Sum of a given size Sub-array---------------------------------------560
Fibonacci-------------------------------------------------------------------802

Chapter-3: Data Structures
Segment Tree Efficient------------------------------------------------------700
Sum of given range (Update any index value) --------------------------------726
Range Minimum Query---------------------------------------------------------648
Nearest Smaller Element-----------------------------------------------------580
Nearest smaller numbers on left side----------------------------------------610

Chapter-4: Algorithm
Binary Search---------------------------------------------------------------216
DFS-------------------------------------------------------------------------313
Mo's Algorithm--------------------------------------------------------------627
Dijkstra (Bellman-Ford with Negative Edge) ---------------------------------350
Fractional Knapsack --------------------------------------------------------452
0-1 Knapsack----------------------------------------------------------------412
Longest Increasing Subsequence----------------------------------------------495
Longest Common Subsequence -------------------------------------------------516
Longest Common Subsequence of 3 --------------------------------------------528
Bellman-Ford's single source shortest path----------------------------------847
Floyd Warshall All Pairs Shortest Path--------------------------------------930
Jobs sequence with deadlines and profits------------------------------------983
Longest Palindromic Subsequence--------------------------------------------1040
Count All Palindromic Subsequence in a given String------------------------1066

Chapter-6: Backtracking
Printing all solutions in N-Queen Problem----------------------------------1090
The Knight’s tour problem--------------------------------------------------1152

*/


/**
*   Normal Template
*/

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

#define     IOS         ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define     int         long long
#define     endl        "\n"
#define     PI          acos(-1.0)
#define     IN          freopen("input.txt",'r',stdin)

const int MOD = 1e9+7;
const int INF = 2e5+5;
const int N = 205;

void solve();
int32_t main()
{
    IOS;
    cout << fixed << setprecision(10);
    int _ = 1;
    cin >> _;
    while(_--) solve();
    return 0;
}

void solve()
{

}

///Must see the constraints range
///Calculate the Time

/**
*   Sieve Prime
*/
vector<int>prime;
bool ok[MOD];

void sieve()
{
    memset(ok, true, sizeof(ok));
    prime.push_back(2);
    ok[0] = ok[1] = false;
    for(int i=3;i<=MOD;i+=2){
        if(ok[i]){
            prime.push_back(i);
            if(i*1*i<=MOD){
                for(int ii=i*i;ii<=MOD;ii += (i+i)){
                    ok[ii] = false;
                }
            }
        }
    }
}

/**
*   Big Mod
**/
int BIGMOD(int b, int p)
{
    int ans = 1 % MOD, x = b % MOD;
    while(p){
        if(p&1)ans = (ans * x)%MOD;
        x = (x*x)%MOD; p >>= 1LL;
    }
    return ans;
}

/**
*  Sum of all Divisors 1 to N
*/
int sum_all_divisors(int num)
{
    int sum = 0;
    for (int i = 1; i <= sqrt(num); i++) {
        int t1 = i * (num / i - i + 1);
        int t2 = (((num/i)*(num/i+1))/2) - ((i*(i+1))/2);
        sum += t1 + t2;
    }
    return sum;
}

/**
*  nCr
*/
void printNcR(int n, int r)
{
    long long p = 1, k = 1;
    if (n - r < r)r = n - r;
    if (r != 0) {
        while (r) {
            p *= n; k *= r;
            long long m = __gcd(p, k);
            p /= m; k /= m;
            n--; r--;
        }
    }
    else p = 1;
    cout << p << endl;
}

/**
*  nPr
*/
int fact(int n)
{
    if (n <= 1) return 1;
    return n * fact(n - 1);
}
int nPr(int n, int r)
{
    return fact(n) / fact(n - r);
}

/**
*   GCD
*/
int GCD(int a, int b){
    return __gcd(a, b);
}

/**
*   LCM
*/
int LCM(int a, int b){
    return ((a*b) / (__gcd(a, b)));
}

/**
*   Number Factorization
*/
int NumberOfFactor(int n)
{
    int cnt = 0;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i == 0)
            cnt++;
        while(n%i == 0)
            n /= i;
    }
    return cnt;
}

/**
*   Prefix Sum
*/
void PrefixSum(int a[], int n)
{
    ///Just sum all the value of it's previous index

    int sum[n];
    sum[0] = a[0];
    for(int i=1;i<n;i++){
        sum[i] = sum[i-1] + a[i];
    }
}

/**
*   Binary Search
*/

///array search with an value
///return bool value
///sort(a, a+n);
///binary_search(a, a + 10, 2);


///Vector
///return bool value
///binary_search(arr.begin(), arr.end(), 15);

///Iterative way
int binarySearch(int arr[], int l, int r, int x)
{
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (arr[m] == x)
            return m;
        if (arr[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }
    return -1;
}
///int result = binarySearch(array, starting, ending, finding value);

/**
*   Base Conversion
*/
int val(char c)
{
    if (c >= '0' && c <= '9')
        return (int)c - '0';
    else
        return (int)c - 'A' + 10;
}
int toDeci(string str, int base)
{
    int len = str.size();
    int power = 1;
    int num = 0;
    for (int i = len - 1; i >= 0; i--) {
        if (val(str[i]) >= base) {
            printf("Invalid Number");
            return -1;
        }
        num += val(str[i]) * power;
        power = power * base;
    }

    return num;
}
char reVal(int num)
{
    if (num >= 0 && num <= 9)
        return (char)(num + '0');
    else
        return (char)(num - 10 + 'A');
}
string fromDeci(int base, int inputNum)
{
    string res = "";
    while (inputNum > 0) {
        res += reVal(inputNum % base);
        inputNum /= base;
    }
    reverse(res.begin(), res.end());
    return res;
}
void convertBase(string s, int a, int b)
{
    int num = toDeci(s, a);
    string ans = fromDeci(b, num);
    cout << ans;
}

///convertBase(string input, from base, to base);


/**
*   AND, OR, XOR
*/

///Number of leading zeroes: builtin_clz(x)
///Number of trailing zeroes : builtin_ctz(x)
///Number of 1-bits: __builtin_popcount(x)

///Bitwise AND (&)
///Bitwise OR (|)
///Bitwise XOR (^)
///Bitwise NOT (!)


/**
*   DFS
*/
void addEdge(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void DFSUtil(int u, vector<int> adj[],
                    vector<bool> &visited)
{
    visited[u] = true;
    cout << u << " ";
    for (int i=0; i<adj[u].size(); i++)
        if (visited[adj[u][i]] == false)
            DFSUtil(adj[u][i], adj, visited);
}

void DFS(vector<int> adj[], int V)
{
    vector<bool> visited(V, false);
    for (int u=0; u<V; u++)
        if (visited[u] == false)
            DFSUtil(u, adj, visited);
}
/**
    int V = 5;
    vector<int> adj[V];
    addEdge(adj, 0, 1);
    DFS(adj, V);
*/


/**
*   Dijkstra (Bellman-Ford with Negative Edge)
*/

class Graph
{
    int V;
    list< pair<int, int> > *adj;

public:
    Graph(int V);
    void addEdge(int u, int v, int w);
    void shortestPath(int s);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list< pair<int, int> >[V];
}

void Graph::addEdge(int u, int v, int w)
{
    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
}

void Graph::shortestPath(int src)
{
    set< pair<int, int> > setds;
    vector<int> dist(V, INF);
    setds.insert(make_pair(0, src));
    dist[src] = 0;
    while (!setds.empty())
    {
        pair<int, int> tmp = *(setds.begin());
        setds.erase(setds.begin());
        int u = tmp.second;
        list< pair<int, int> >::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
        {
            int v = (*i).first;
            int weight = (*i).second;
            if (dist[v] > dist[u] + weight)
            {
                if (dist[v] != INF)
                    setds.erase(setds.find(make_pair(dist[v], v)));
                dist[v] = dist[u] + weight;
                setds.insert(make_pair(dist[v], v));
            }
        }
    }
    printf("Vertex Distance from Source\n");
    for (int i = 0; i < V; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
}

lol_main()
{
    int V = 9;
    Graph g(V);
    g.addEdge(0, 1, 4);
    g.shortestPath(0);
}

/**
*   0-1 Knapsack
*/

int knapSack(int W, int wt[], int val[], int n)
{
    int i, w;
    int K[2][W + 1];
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                K[i % 2][w] = 0;
            else if (wt[i - 1] <= w)
                K[i % 2][w] = max(
                    val[i - 1]
                        + K[(i - 1) % 2][w - wt[i - 1]],
                    K[(i - 1) % 2][w]);
            else
                K[i % 2][w] = K[(i - 1) % 2][w];
        }
    }
    return K[n % 2][W];
}

int knapSack(int W, int wt[], int val[], int n)
{
    int dp[W + 1];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i < n + 1; i++) {
        for (int w = W; w >= 0; w--) {
            if (wt[i - 1] <= w)
                dp[w] = max(dp[w], dp[w - wt[i - 1]] + val[i - 1]);
        }
    }
    return dp[W];
}

///Knapsack(Capacity, Weight, Value, Item Size)

/**
*   Fractional Knapsack
*/
struct Item {
    int value, weight;
    Item(int value, int weight)
    {
       this->value=value;
       this->weight=weight;
    }
};
bool cmp(struct Item a, struct Item b)
{
    double r1 = (double)a.value / (double)a.weight;
    double r2 = (double)b.value / (double)b.weight;
    return r1 > r2;
}

double fractionalKnapsack(int W, struct Item arr[], int n)
{
    sort(arr, arr + n, cmp);

    int curWeight = 0;
    double finalvalue = 0.0;
    for (int i = 0; i < n; i++) {
        if (curWeight + arr[i].weight <= W) {
            curWeight += arr[i].weight;
            finalvalue += arr[i].value;
        }
        else {
            int remain = W - curWeight;
            finalvalue += arr[i].value * ((double)remain / (double)arr[i].weight);
            break;
        }
    }
    return finalvalue;
}

///Item arr[] = { { 60, 10 }, { 100, 20 }, { 120, 30 } };
///fractionalKnapsack(W, arr, n);


/**
*   Longest Increasing Subsequence
*/
int LongestIncreasingSubsequenceLength(vector<int>& v)
{
    if (v.size() == 0)
        return 0;
    vector<int> tail(v.size(), 0);
    int length = 1;
    tail[0] = v[0];
    for (int i = 1; i < v.size(); i++) {
        auto b = tail.begin(), e = tail.begin() + length;
        auto it = lower_bound(b, e, v[i]);
        if (it == tail.begin() + length)
            tail[length++] = v[i];
        else
            *it = v[i];
    }
    return length;
}


/**
*   Longest Common Subsequence
*/
int lcs( char *X, char *Y, int m, int n )
{
    if (m == 0 || n == 0)
        return 0;
    if (X[m-1] == Y[n-1])
        return 1 + lcs(X, Y, m-1, n-1);
    else
        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

int lcsOf3(int i, int j,int k)
{
    if(i==-1||j==-1||k==-1)
        return 0;
    if(dp[i][j][k]!=-1)
        return dp[i][j][k];

    if(X[i]==Y[j] && Y[j]==Z[k])
        return dp[i][j][k] = 1+lcsOf3(i-1,j-1,k-1);
    else
        return dp[i][j][k] = max(max(lcsOf3(i-1,j,k), lcsOf3(i,j-1,k)),lcsOf3(i,j,k-1));
}


/**
*   Minimum Sub Array Sum
*/
int smallestSumSubarr(int arr[], int n)
{
    int min_ending_here = INT_MAX;
    int min_so_far = INT_MAX;
    for (int i=0; i<n; i++){
        if (min_ending_here > 0)
            min_ending_here = arr[i];
        else
            min_ending_here += arr[i];
        min_so_far = min(min_so_far, min_ending_here);
    }
    return min_so_far;
}

/**
*   Maximum Sum of a given size Sub-array
*/
int maxSum(int arr[], int n, int k)
{
    if (n < k){
       cout << "Invalid";
       return -1;
    }
    int res = 0;
    for (int i=0; i<k; i++)
       res += arr[i];
    int curr_sum = res;
    for (int i=k; i<n; i++){
       curr_sum += arr[i] - arr[i-k];
       res = max(res, curr_sum);
    }

    return res;
}

/**
*   Nearest Smaller Element
*/
void printNSE(int arr[], int n)
{
    stack<pair<int, int> > s;
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        int next = arr[i];
        if (s.empty()) {
            s.push({ next, i });
            continue;
        }
        while (!s.empty() && s.top().first > next) {
            ans[s.top().second] = next;
            s.pop();
        }

        s.push({ next, i });
    }
    while (!s.empty()) {
        ans[s.top().second] = -1;
        s.pop();
    }
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ---> " << ans[i] << endl;
    }
}

/**
*   Nearest smaller numbers on left side
*/
nearest smaller numbers on left side
void printPrevSmaller(int arr[], int n)
{
    stack<int> S;
    for (int i=0; i<n; i++)
    {
        while (!S.empty() && S.top() >= arr[i])
            S.pop();
        if (S.empty()) cout << "_, ";
        else cout << S.top() << ", ";
        S.push(arr[i]);
    }
}

/**
*   Mo's Algorithm
*/
struct Query
{
    int L, R;
};

void printQuerySums(int a[], int n, Query q[], int m)
{
    for (int i=0; i<m; i++)
    {
        int L = q[i].L, R = q[i].R;
        int sum = 0;
        for (int j=L; j<=R; j++)
            sum += a[j];
        cout << "Sum of [" << L << ", "
            << R << "] is "  << sum << endl;
    }
}

/**
*   Range Minimum Query
*/
int lookup[MAX][MAX];

struct Query {
    int L, R;
};
void preprocess(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        lookup[i][0] = i;
    for (int j = 1; (1 << j) <= n; j++){
        for (int i = 0; (i + (1 << j) - 1) < n; i++){
            if (arr[lookup[i][j - 1]] < arr[lookup[i + (1 << (j - 1))][j - 1]])
                lookup[i][j] = lookup[i][j - 1];
            else
                lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1];
        }
    }
}
int query(int arr[], int L, int R)
{
    int j = (int)log2(R - L + 1);
    if (arr[lookup[L][j]] <= arr[lookup[R - (1 << j) + 1][j]])
        return arr[lookup[L][j]];
    else
        return arr[lookup[R - (1 << j) + 1][j]];
}
void RMQ(int arr[], int n, Query q[], int m)
{
    preprocess(arr, n);
    for (int i = 0; i < m; i++)
    {
        int L = q[i].L, R = q[i].R;
        cout << "Minimum of [" << L << ", " << R << "] is " << query(arr, L, R) << endl;
    }
}
int main()
{
    int a[] = { 7, 2, 3, 0, 5, 10, 3, 12, 18 };
    int n = sizeof(a) / sizeof(a[0]);
    Query q[] = { { 0, 4 }, { 4, 7 }, { 7, 8 } };
    int m = sizeof(q) / sizeof(q[0]);
    RMQ(a, n, q, m);
    return 0;
}

/**
*   Segment Tree Efficient
*/
int n;
int tree[2 * N];
void build( int arr[]){
    for (int i=0; i<n; i++) tree[n+i] = arr[i];
    for (int i = n - 1; i > 0; --i)
        tree[i] = tree[i<<1] + tree[i<<1 | 1];
}
void updateTreeNode(int p, int value){
    tree[p+n] = value; p = p+n;
    for (int i=p; i > 1; i >>= 1)
        tree[i>>1] = tree[i] + tree[i^1];
}
int query(int l, int r){
    int res = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1){
        if (l&1) res += tree[l++];
        if (r&1) res += tree[--r];
    }
    return res;
}
int main(){
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    build(a);
    updateTreeNode(2, 1);
    cout << query(1, 3)<<endl;
}

/**
*   Sum of given range (Update any index value)
*/
int getMid(int s, int e) { return s + (e -s)/2; }

int getSumUtil(int *st, int ss, int se, int qs, int qe, int si){
    if (qs <= ss && qe >= se) return st[si];
    if (se < qs || ss > qe) return 0;
    int mid = getMid(ss, se);
    return getSumUtil(st, ss, mid, qs, qe, 2*si+1) + getSumUtil(st, mid+1, se, qs, qe, 2*si+2);
}
void updateValueUtil(int *st, int ss, int se, int i, int diff, int si){
    if (i < ss || i > se) return;
    st[si] = st[si] + diff;
    if (se != ss){
        int mid = getMid(ss, se);
        updateValueUtil(st, ss, mid, i, diff, 2*si + 1);
        updateValueUtil(st, mid+1, se, i, diff, 2*si + 2);
    }
}
void updateValue(int arr[], int *st, int n, int i, int new_val){
    if (i < 0 || i > n-1)
    {
        cout<<"Invalid Input";
        return;
    }
    int diff = new_val - arr[i];
    arr[i] = new_val;
    updateValueUtil(st, 0, n-1, i, diff, 0);
}
int getSum(int *st, int n, int qs, int qe){
    if (qs < 0 || qe > n-1 || qs > qe) {
        cout<<"Invalid Input"; return -1;
    } return getSumUtil(st, 0, n-1, qs, qe, 0);
}
int constructSTUtil(int arr[], int ss, int se, int *st, int si){
    if (ss == se) {
        st[si] = arr[ss];
        return arr[ss];
    }
    int mid = getMid(ss, se);
    st[si] = constructSTUtil(arr, ss, mid, st, si*2+1) +
                constructSTUtil(arr, mid+1, se, st, si*2+2);
    return st[si];
}
int *constructST(int arr[], int n){
    int x = (int)(ceil(log2(n)));
    int max_size = 2*(int)pow(2, x) - 1;
    int *st = new int[max_size];
    constructSTUtil(arr, 0, n-1, st, 0);
    return st;
}

int main(){
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    int *st = constructST(arr, n);
    cout<<"Sum of values in given range = "<<getSum(st, n, 1, 3)<<endl;
    updateValue(arr, st, n, 1, 10);
    cout<<"Updated sum of values in given range = " <<getSum(st, n, 1, 3)<<endl;
    return 0;
}

/**
*   Is Factorial of any number or not
*/
bool isFactorial(int n){
  for (int i = 1;; i++) {
    if (n % i == 0) n /= i;
    else break;
  }
  if (n == 1) return true;
  else return false;
}


/**
*   Fibonacci
*/
ll I[N][N],T[N][N];

void mul(ll A[][N],ll B[][N],ll dim){
    ll res[dim+1][dim+1];
    for(ll i=0;i<dim;i++)
    {
        for(ll j=0;j<dim;j++)
        {
            res[i][j]=0;
            for(ll k=0;k<dim;k++)
            {
                ll x=(A[i][k]*B[k][j])%mod;
                res[i][j]=(res[i][j]+x)%mod;
            }
        }
    }
    for(ll i=0;i<2;i++)
    {
        for(ll j=0;j<2;j++)A[i][j]=res[i][j];
    }
}
void solve(ll a,ll b,ll n){
    I[0][0]=I[1][1]=1;
    I[0][1]=I[1][0]=0;

    T[0][0]=0;
    T[0][1]=T[1][0]=T[1][1]=1;
    n--;
    while(n){
        if(n%2==1){
            mul(I,T,2);
            n--;
        }
        else{
            mul(T,T,2);
            n/=2;
        }
    }
    ll ans=a*I[0][1]+b*I[1][1];
    cout<<ans%mod<<nl;
}

/**
*   Bellman-Ford's single source shortest path
*/
#include <bits/stdc++.h>
struct Edge {
    int src, dest, weight;
};

struct Graph {
    int V, E;
    struct Edge* edge;
};

struct Graph* createGraph(int V, int E){
    struct Graph* graph = new Graph;
    graph->V = V;
    graph->E = E;
    graph->edge = new Edge[E];
    return graph;
}

void printArr(int dist[], int n)
{
    printf("Vertex Distance from Source\n");
    for (int i = 0; i < n; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
}

/// The main function that finds shortest distances from source
/// to all other vertices using Bellman-Ford algorithm. The
/// function also detects negative weight cycle
void BellmanFord(struct Graph* graph, int src)
{
    int V = graph->V;
    int E = graph->E;
    int dist[V];
    /// Step 1: Initialize distances from source to all other
    /// Vertice's's as INFINITE
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;
    /// Step 2: Relax all edges |V| - 1 times. A simple
    /// shortest path from source to any other vertex can have
    /// at-most |V| - 1 edges
    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }

    /// Step 3: check for negative-weight cycles. The above
    /// step guarantees shortest distances if graph doesn't
    /// contain negative weight cycle. If we get a shorter
    /// path, then there is a cycle.
    for (int i = 0; i < E; i++) {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        int weight = graph->edge[i].weight;
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
            printf("Graph contains negative weight cycle");
            return;
        }
    }
    printArr(dist, V);
}

int main()
{
    int V = 5; /// Number of vertices in graph
    int E = 8; /// Number of edges in graph
    struct Graph* graph = createGraph(V, E);

    /// add edge 0-1 (or A-B in above figure)
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = -1;

    BellmanFord(graph, 0);
}

/**
*   Floyd Warshall All Pairs Shortest Path
*/

void printSolution(int dist[][V]);

void floydWarshall(int graph[][V])
{
    int dist[V][V], i, j, k;

    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];

    for (k = 0; k < V; k++) {
        for (i = 0; i < V; i++) {
            for (j = 0; j < V; j++) {
                if (dist[i][j] > (dist[i][k] + dist[k][j]) && (dist[k][j] != INF
                                && dist[i][k] != INF))
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
    printSolution(dist);
}

void printSolution(int dist[][V])
{
    cout << "The following matrix shows the shortest " "distances"
            " between every pair of vertices \n";
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF)
                cout << "INF" << "     ";
            else
                cout << dist[i][j] << "     ";
        }
        cout << endl;
    }
}

int main()
{
    int graph[V][V] = { { 0, 5, INF, 10 },
                        { INF, 0, 3, INF },
                        { INF, INF, 0, 1 },
                        { INF, INF, INF, 0 } };

    floydWarshall(graph);
    return 0;
}

/**
*   Jobs sequence with deadlines and profits
*/
struct Job{
    char id;
    int deadLine, profit;
};
struct DisjointSet{
    int *parent;
    DisjointSet(int n){
        parent = new int[n+1];
        for (int i = 0; i <= n; i++)
            parent[i] = i;
    }
    int find(int s){
        if (s == parent[s])
            return s;
        return parent[s] = find(parent[s]);
    }
    void merge(int u, int v){
        parent[v] = u;
    }
};
bool cmp(Job a, Job b){
    return (a.profit > b.profit);
}
int findMaxDeadline(struct Job arr[], int n)
{
    int ans = INT_MIN;
    for (int i = 0; i < n; i++)
        ans = max(ans, arr[i].deadLine);
    return ans;
}

int printJobScheduling(Job arr[], int n)
{
    sort(arr, arr + n, cmp);
    int maxDeadline = findMaxDeadline(arr, n);
    DisjointSet ds(maxDeadline);
    for (int i = 0; i < n; i++){
        int availableSlot = ds.find(arr[i].deadLine);
        if (availableSlot > 0){
            ds.merge(ds.find(availableSlot - 1), availableSlot);
            cout << arr[i].id << " ";
        }
    }
}

int main()
{
    Job arr[] = { { 'a', 2, 100 }, { 'b', 1, 19 }, { 'c', 2, 27 }, { 'd', 1, 25 },
                { 'e', 3, 15 } };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Following jobs need to be " << "executed for maximum profit\n";
    printJobScheduling(arr, n);
    return 0;
}

/**
*   Longest Palindromic Subsequence
*/
int lps(char *str)
{
    int n = strlen(str);
    int i, j, cl;
    int L[n][n];
    for (i = 0; i < n; i++)
      L[i][i] = 1;

    for (cl=2; cl<=n; cl++){
        for (i=0; i<n-cl+1; i++){
            j = i+cl-1;
            if (str[i] == str[j] && cl == 2)
               L[i][j] = 2;
            else if (str[i] == str[j])
               L[i][j] = L[i+1][j-1] + 2;
            else
               L[i][j] = max(L[i][j-1], L[i+1][j]);
        }
    }
    return L[0][n-1];
}

/**
*   Count All Palindromic Subsequence in a given String
*/
int n, dp[1000][1000];
string str = "abcb";

int countPS(int i, int j)
{
    if (i > j)
        return 0;
    if (dp[i][j] != -1)
        return dp[i][j];
    if (i == j)
        return dp[i][j] = 1;
    else if (str[i] == str[j])
        return dp[i][j] = countPS(i + 1, j) + countPS(i, j - 1) + 1;
    else
        return dp[i][j] = countPS(i + 1, j) + countPS(i, j - 1) - countPS(i + 1, j - 1);
}

///memset(dp, -1, sizeof(dp));
///countPS(0, n - 1) << endl;


/**
*   Printing all solutions in N-Queen Problem
*/
vector<vector<int> > result;
void solveBoard(vector<vector<char> >& board, int row,
                int rowmask, int ldmask, int rdmask, int& ways)
{
    int n = board.size();
    int all_rows_filled = (1 << n) - 1;
    if (rowmask == all_rows_filled) {

        vector<int> v;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board.size(); j++) {
                if (board[i][j] == 'Q')
                    v.push_back(j + 1);
            }
        }
        result.push_back(v);
        return;
    }

    int safe = all_rows_filled & (~(rowmask | ldmask | rdmask));
    while (safe) {
        int p = safe & (-safe);
        int col = (int)log2(p);
        board[row][col] = 'Q';

        solveBoard(board, row + 1, rowmask | p, (ldmask | p) << 1, (rdmask | p) >> 1, ways);
        safe = safe & (safe - 1);
        board[row][col] = ' ';
    }
    return;
}


int main()
{
    int n = 4;
    int ways = 0;

    vector<vector<char> > board;
    for (int i = 0; i < n; i++) {
        vector<char> tmp;
        for (int j = 0; j < n; j++) {
            tmp.push_back(' ');
        }
        board.push_back(tmp);
    }
    int rowmask = 0, ldmask = 0, rdmask = 0;
    int row = 0;
    result.clear();
    solveBoard(board, row, rowmask, ldmask, rdmask, ways);
    sort(result.begin(),result.end());
    for (auto ar : result) {
        cout << "[";
        for (auto it : ar) cout << it << " ";
        cout << "]";
    }
    return 0;
}

/**
*   The Knight’s tour problem
*/
#define N 8

int solveKTUtil(int x, int y, int movei, int sol[N][N],
                int xMove[], int yMove[]);

int isSafe(int x, int y, int sol[N][N]){
    return (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}

void printSolution(int sol[N][N])
{
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++)
            cout << " " << setw(2) << sol[x][y] << " ";
        cout << endl;
    }
}

int solveKT()
{
    int sol[N][N];
    for (int x = 0; x < N; x++)
        for (int y = 0; y < N; y++)
            sol[x][y] = -1;
    int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
    int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
    sol[0][0] = 0;
    if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == 0) {
        cout << "Solution does not exist";
        return 0;
    }
    else
        printSolution(sol);
    return 1;
}

int solveKTUtil(int x, int y, int movei, int sol[N][N],
                int xMove[8], int yMove[8])
{
    int k, next_x, next_y;
    if (movei == N * N) return 1;
    for (k = 0; k < 8; k++) {
        next_x = x + xMove[k];
        next_y = y + yMove[k];
        if (isSafe(next_x, next_y, sol)) {
            sol[next_x][next_y] = movei;
            if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove) == 1)
                return 1;
            else
                sol[next_x][next_y] = -1;
        }
    }
    return 0;
}

int main(){
    solveKT();
    return 0;
}