All submissions for this problem are available.

Given two matrices A and B. Both have N rows and M columns. In the matrix A, numbers from 1 to MN have been written in row major order. Row major order numbers cells from left to right, and top to bottom. That is,

           1                  2                 3             ...     M
A  =    M+1             M+2            M+3        ...     2M
          2M+1           2M+2          2M+3       ...   3M
           .                   .                  .              ...      .
           .                   .                  .               ...      .
         (N-1)M+1    (N-1)M+2    (N-1)M+3   ...   NM

Similarly, in the matrix B, numbers from 1 to MN have been written in column major order. Column major order numbers cells from top to bottom and left to right.

You are to count number of pairs (i,j) such that A_i,j=B_i,j.

Input

The input consists of multiple test cases. The first line of input contains a single integer T, the number of test cases. T test cases follow. Each test case is described by one line containing two space separated integers,N and M

Output

Output T lines, i^th line containing answer of the i^th test case.

Constraints

1 ≤ T ≤ 10⁵

1 ≤ N, M ≤ 10⁹

Example

Input:
1
4 5


Output:
2

Explanation

For the first case two matrices look as follows:


A=

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

B=

1 5 9 13 17

2 6 10 14 18

3 7 11 15 19

4 8 12 16 20

A_1,1=B_1,1

A_4,5=B_4,5

_Explanation

Practice
Contest

Author: Roman Rubanenko
Tester/Editorialist: Utkarsh Lath

Difficulty:

Simple

Pre-requisites:

High school maths

Problem:

Given two matrices A and B, both of them having N rows and M columns. The cells of A are numbered in row major order, and cells of B are numbered in column major order. How many cells appears at the same location in both the orderings ?

Explanation:

For 0 ≤ i < N, 0 ≤ j < M, the (i,j)^th entries are:

A_{i, j} = i * M + j + 1
B_{i, j} = j * N + i + 1

equating the two, we get

    i * M + j + 1 = j * N + i + 1
⇒ i * (M-1) = j * (N-1)
⇒ i / j = (N-1) / (M-1) = p / q
⇒ i = l * p, j = l * q for 0 ≤ l ≤ min((N-1) / p, (M-1)/q)

where p/q is reduced form of (N-1)/(M-1).

However, if g = gcd(N-1, M-1),

(p, q) = ((N-1)/g, (M-1)/g)

Therefore, (N-1) / p = (M-1) / q = g
and the cells which get same numbering are (l * p, l * q) for 0 ≤ l ≤ g, which are g+1 in number.

Boundary cases

N = 1 or M = 1, in which case the answer is max(N, M).

#include"stdio.h"

int gcd(int a, int b) {

    if(a<b) return gcd(b,a);

    int c;

    while(b)

        c = a%b, a = b, b = c;

    return a;

}

int main() {

    int T;

    scanf("%d", &T);

    while(T--) {

        int a, b;

        scanf("%d%d", &a, &b);

        printf("%d\n", 1+gcd(a-1, b-1));

    }

}

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N−1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump.

Initially, you have a tank of infinite capacity carrying no petrol. You can start the tour at any of the petrol pumps. Calculate the first point from where the truck will be able to complete the circle. Consider that the truck will stop at each of the petrol pumps. The truck will move one kilometer for each litre of the petrol.

Input Format

The first line will contain the value of N.
The next N lines will contain a pair of integers each, i.e. the amount of petrol that petrol pump will give and the distance between that petrol pump and the next petrol pump.

Constraints:
1≤N≤105
1≤amount of petrol, distance≤109

Output Format

An integer which will be the smallest index of the petrol pump from which we can start the tour.

Sample Input

3
1 5
10 3
3 4

Sample Output

1

Explanation

We can start the tour from the second petrol pump.

Copyright © 2015 HackerRank.

Consider the amount of fuel you have in your tank as a function of the amount of stations you have passed (the integral of the change in fuel {gained - used} per station results in the amount of fuel for every station, the fundamental theorem of calculus). Now: this function has to be positive for every station because you cannot ever have negative fuel in your tank. This only happens whenever you start at a global minimum of this function. You are essentially shifting the function vertically, setting it to zero at your starting point and if this is the lowest point then all other points will be positive. 

This is assuming that a full circle will not result in a net fuel loss (then you cannot complete the circle) and furthermore that there are no more than 1 global minima (then you get stuck with exactly 0 fuel at the position of the second global minimum).

Code

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int n, p[100005], d[100005];

int main() {

    scanf("%d", &n);

    for (int i = 0; i < n; ++i) scanf("%d%d", &p[i], &d[i]);

    int ret = 0, amount = 0, sum = 0;

    for (int i = 0; i < n; ++i) {

        p[i] -= d[i];

        sum += p[i];

        if (amount + p[i] < 0) {

            amount = 0;

            ret = i + 1;

            cout<<"setting res at pos  "<<i<<" as "<<i+1<<endl;

        } else amount += p[i];

    }

    printf("%d\n", sum >= 0 ? ret : -1);

    return 0;

}

Prof. Vasechkin wants to represent positive integer n as a sum of addends, where each addends is an integer number containing only1s. For example, he can represent 121 as 121=111+11+–1. Help him to find the least number of digits 1 in such sum.

Input

The first line of the input contains integer n (1 ≤ n < 1015).

Output

Print expected minimal number of digits 1.

A dfs type of recursion .nice one

#include<bits/stdc++.h>

using namespace std;

#define ll long long int 

ll pow11[20];

int countdig(ll num)

{

int res=0;

 while(num!=0)

 {

  num=num/10;

  res++;

 }

 return res;

}

int cntst=0;

ll ans=100000000;

void solve(ll num,int steps)

{

       if(steps>ans)

       return ;

   //    cout<<num<<endl;

       if(num==0)

       {

           ans=steps;

           return ;

}

 ll val=1;

 int temp=1;

 while(val*10+1<=num)

 {

    val=val*10+1;

    temp++;

}

ll v2=val*10+1;

// cout<<"val "<<val<<" "<<v2<<endl;

 solve(num%val,steps+temp*(num/val));

 solve(v2-num,steps+temp+1);       

  

}

void pre()

{

  pow11[1]=1;

 for(int i=2;i<=16;i++)

 {

   pow11[i]=10*pow11[i-1]+1;

 }

 

}

int main()

{

  ll n;

  pre();

  cin>>n;

  solve(n,0);

  cout<<ans<<endl;

}