## 2017ICPC北京网络赛 G | hihocoder 1584 Bounce

For Argo, it is very interesting watching a circle bouncing in a rectangle.

As shown in the figure below, the rectangle is divided into N×M grids, and the circle fits exactly one grid.

The bouncing rule is simple:

1. The circle always starts from the left upper corner and moves towards lower right.

2. If the circle touches any edge of the rectangle, it will bounce.

3. If the circle reaches any corner of the rectangle after starting, it will stop there.

Argo wants to know how many grids the circle will go through only once until it first reaches another corner. Can you help him?

### 输入

The input consists of multiple test cases. (Up to 105)

For each test case:

One line contains two integers N and M, indicating the number of rows and columns of the rectangle. (2 ≤ N, M ≤ 109)

### 输出

For each test case, output one line containing one integer, the number of grids that the circle will go through exactly once until it stops (the starting grid and the ending grid also count).

n=3，m=6时L=gcd(2,5)=1，n=9，m=15时L=gcd(8,14)=2。

## 2017ICPC北京网络赛 B | hihocoder 1579 Reverse Suffix Array

### 描述

There is a strong data structure called “Suffix Array” which can effectively solve string problems.

Let S=s1s2…sn be a string and let S[i,j] denote the substring of S ranging from i to j. The suffix array A of S is now defined to be an array of integers providing the starting positions of suffixes of S in lexicographical order. This means, an entry A[i] is the starting position of the i-th smallest suffix in S and thus for all 1 < i ≤ n:  S[A[i-1], n] < S[A[i], n].

For example: the suffix array of “banana” is [6, 4, 2, 1, 5, 3].

Here comes another problem called “Reverse Suffix Array”.

Given a suffix array, you need to figure out how many lower case strings are there whose suffix array is the same as the given suffix array.

### 输入

First line contains a positive number T which means the number of test cases.

For each test cases, first line contains a positive number N, the second line contains N integer(s) which indicates the suffix array A.

1 ≤ T ≤ 10, 1 ≤ N ≤ 100,000

1 ≤ A[i] ≤ N (i = 1…N)

### 输出

For each test case, output one line contains the answer. If no qualified string exists, output 0.

sa数组4 3 2 5 1可以画成下面：
④⑤
③④⑤
②③④⑤

①②③④⑤