GCD and Euclid's algorithm

ID 18692. Long gcd

ID 30770. Single GCD

ID 37550. Father and daughter

Dad step length – And see, and the little daughter's – In cm. They begin to walk, putting their feet on one mark. How far will they walk before their feet are level again?

Write the solution to the problem as a function solve(A, B) that returns the answer. You don't need to enter or withdraw anything!

Examples

ID 37551. Math competition

At the mathematical competition, the guys played the fascinating ancient Chinese puzzle Tangram. In one game set there were A acute-angled triangles, and in the other - B obtuse-angled triangles. What is the smallest number of participants who can use sets of the same number of each type of triangles?

Write the solution to the problem as a function solve(A, B) that returns the answer. You don't need to enter or withdraw anything!

Examples

ID 37552. orchids

In the greenhouse, they planted different varieties of orchids in 2 rows. Flowers of one variety were placed at a distance of A cm between plants, and the other - at B cm. How far will the orchids of both varieties be next to each other? 

Write the solution to the problem as a function solve(A, B) that returns the answer. You don't need to enter or withdraw anything!

Examples

ID 37553. Amount of information

A student in his first year downloaded an average of A Kb of information per day from the Internet, and in his second year – In Kbytes, paying the same amount of money for the received Internet traffic per week. What is the smallest amount of information in Kbytes he downloaded in a week?

Write the solution to the problem as a function solve(A, B) that returns the answer. You don't need to enter or withdraw anything!

Examples

ID 37554. Vietnamese craftsmen

Vietnamese folk craftsmen make decorative panels from pieces of rice straw, sticking them on boards. What is the smallest length (in mm) that the straw must be so that it can be cut into equal parts along A mm and B mm without cutting?

Write the solution to the problem as a function solve(A, B) that returns the answer. You don't need to enter or withdraw anything!

Examples

ID 21815. NOD and NOC

ID 12482. ordered fractions

Examples

ID 30777. oranges

Katya decided to invite n friends to visit her. Since her friends are very fond of fruits, she bought m identical oranges as a treat for them. She wants to cut each orange into the same number of equal slices so that they can be distributed among the guests (Katya herself will not eat oranges), and everyone gets the same number of slices.

Write a program that calculates the minimum number of slices each orange must be cut into to satisfy the above conditions.
 

Examples

ID 12483. squares

At the labor lesson, everyone was given a rectangle with sides measuring A and B (whole, \( 1 <= A, B <= 2^{31} - 1\)). The boy Senya is very fond of cutting rectangles with special cynicism, and when the teacher invites everyone to cut out squares from a rectangle, Senya acts very cunningly. With one cut parallel to the side of the rectangle, he cuts off from the rectangle a square with a side equal to the smallest side of the rectangle and continues to do the same procedure with the part remaining after the cut. If a part turns out to be a square, then Senya calms down and begins to count the resulting squares.
How many squares will he cut?

Input
The numbers A and B are specified on the same line separated by a space.

Imprint
The number of resulting squares.
 

Examples

ID 31872. Add two fractions

Examples

ID 29423. Fraction reduction

ID 34852. Long gcd

Examples

ID 18691. Short GCD

Examples

ID 24905. NOD and NOC

Examples

ID 38258. Stew

Summer was approaching, and Igor, Gena and Denis decided to go camping together, just like last year. Almost all issues have already been resolved: the route has already been worked out, train tickets have been bought, a four-seater tent has been found in Denis’s closet, and under Igor’s bed — axe. It remains only to solve the issue with the products.

Last year, the guys honestly admitted that they did not know how much food they needed, and asked their classmate Nastya to help, who made a shopping list for them. But this year, asking her again is somehow undignified. One could look at how much they bought last year and take the same amount, but none of the guys had any receipts or a grocery list.

But they still have correspondence on the social network, where they argued over who would carry how many cans of stew. In this correspondence, Igor first suggested dividing the whole canned meat in relation to a: b: c, so that Igor himself would bear the first part, the second — Gena, and the third — Denis. But Denis did not like it, and he suggested changing the ratio to d: e: f.

After some more thinking, the guys realized that they still wouldn’t cut the cans of stew, and, therefore, both ratios were chosen so that each in both cases got an integer number of cans.

Given two ratios a: b: c and d: e: f, calculate how many cans of stew the guys bought for last year's trip. From all possible answers print the minimum. The guys remember that they definitely had at least one can of stew.

Input
The first line contains three positive integers a, b, c separated by spaces. The second line contains three positive integers d, e, f, also separated by spaces.

All numbers are less than 1000.

Imprint
Print a positive integer — number of cans of stew.
 

Examples

ID 38300. Buses

Berland has a deplorable situation with intercity bus service. There are only three bus routes in the whole country, each of which runs only one bus. On the first day of the new year, at exactly midnight, all three buses depart on their routes from the capital of Berland. It is known that the first bus needs a minutes to cover the whole route and return to the capital, the second — b minutes, and the third — c minutes. Thus, the first bus departs from the capital of Berland at times 0, a, 2a, 3a, the second — at times 0, b, 2b, 3b , and the third at times 0, c, 2c, 3c .

The moment of time is called suitable for transfer if at this moment all three buses depart from the capital of Berland. For example, if a=1, b=2, c=1, then times 0 and 2 are eligible for transfers, but time 1 is not, because at that time a second bus is on the way. Berland — a special country with a special measurement of time, so there are exactly t minutes in a Berland day. This means that on the first day all moments of time from 0 to (t & minus; 1) inclusive occur, on the second day — from the t-th to (2t−1)-th inclusive, to the third — from 2t to (3t−1) inclusive and so on.

The Ministry of Transport of Berland was interested in how many suitable time points for a transfer will occur on the d-th day in Berland. Unfortunately, local officials are busy with other matters, so you have been assigned to answer this question.

Input
Five lines contain five integers a, b, c, t  and d (1≤a, b, c≤10⁶ , 1≤t, d≤10⁹ ) — the time of the complete passage of the route by the first, second and third buses, respectively, the number of minutes in a day and the number of the day, which is of interest to the Ministry of Transport of Berland.

Imprint
Print a single integer — the number of times suitable for transplantation on the d-th day.

Examples

ID 38323. Segment_0

On checkered paper, Petya drew a segment from a point with coordinates (a,b) to a point with coordinates (c,d). How many cells does this segment pass through?
Input
Integers a, b, c, d are entered. Modulo numbers do not exceed 10⁹.

Imprint
Print one number — the number of cells through which the segment passes.

Examples

ID 38432. Integer points

A polygon (not necessarily convex) on a plane is given by the coordinates of its vertices. It is required to count the number of points with integer coordinates lying inside it (but not on its border).

Input data format
    The first line contains N (3 ≤N ≤1000) – the number of vertices of the polygon. The next N lines contain the coordinates (X_i, Y_i) of the polygon vertices in clockwise order. Xi and Yi are integers, modulo not exceeding 1000000.

Output data format
Output a single number – desired number of points.

Examples

ID 38584. Many hours

Gromozeka has N hours. The ith clock hand (\(1<=i<=N\)) is rotated 360 ° exactly Ti seconds. Initially, the hand of all clocks stands still and points straight up. Gromozeka starts all the clocks at the same time. After how many seconds will the hand of all clocks point straight up again?

Input
The first line contains an integer N (\(1<=N<=100\)). The following N lines contain integers Ti (\(1<=T_i<= 10^{18}\)), one number per line. 

Imprint
Display the answer. It is guaranteed that the answer does not exceed \(10^{18}\).
 

Examples

ID 38847. Cinema

Marya Ivanovna and Marya Mikhailovna led the schoolchildren to the cinema. So that there would be no offense, Marya Ivanovna lined up all the schoolchildren in alphabetical order and seated them: first in the first row from left to right, then in the second from left to right, etc., filling the entire hall of n rows of m seats. Then Marya Mikhailovna came and said that the guys sat down incorrectly – need to transfer. She suggested first filling all the first places from the first row to the last, then all the second places, and so on.

Determine how many schoolchildren will remain in their place after such a transplant.

For example, if n = 3 and m = 3, then in the first case the children will sit like this:

1    2    3
4    5    6
7    8    9
and in the second – like this:
1    4    7
2    5    8
3    6    9
Thus, three students: 1, 5 and 9 will remain in their places.

Input
Enter two integers n and m (1 ≤ n, m ≤ 10⁹ ).

Imprint
Output the number of schoolchildren who will remain in their places.
 

Examples

ID 38877. Greatest Common Divisor

The greatest common divisor of a non-empty collection of natural numbers A is the maximum natural number d such that it is simultaneously a divisor of all numbers in the set A.
Given an array of natural numbers [a₁, a₂, . . . , a_n] and number k. It is required to choose a subarray of k consecutive elements [a_l, a_l+1, . . . , a_l+k−1] so that their greatest common divisor is as large as possible, and output this greatest common divisor.

Input
The first input line contains two integers n and k (2 ≤ n ≤ 500 000, 2 ≤ k ≤ n).
The second line contains n natural numbers a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10¹⁸).

Imprint
Print one natural number — the maximum possible value of the greatest common divisor of the elements of a subarray of length k of the given array.

Examples

ID 39392. Walk Gromozeka and Alice

Gromozeka and Alice are old friends. When they meet on some planet, they constantly go to a cafe. But Alice doesn't like to go to every a cafe, and Gromozeka doesn't like to go to every g cafe. In order not to offend anyone, they do not go to those cafes that Alice and Gromozeka do not want to go to at the same time. On their next walk, they have a N cafe on their way. How many cafes can they go to?

Input
The only line contains three integers - a , g , N ( 1 <= a , g , N <= 10 ⁹ ).

Imprint
Print a single integer - the number of cafes that Gromozeka and Alice can visit.
 

Examples

ID 43128. Regular operations on an array

It was a normal weekday evening in Magnitogorsk. Phil and Cosmos were returning home by car after a hard shift. Here Kosmos remembered that Bely had given him a task that he had safely forgotten to complete. To protect Kosmos from the wrath of Sasha Bely, help him complete the task.
Given n integers a₁,a₂,...,a_n. It is required to make the greatest common divisor (GCD) of all numbers in the array equal to 1. In one operation, you can do the following:
     Choose an arbitrary index in array 1 <= i <= n;
     Make a_i = gcd(a_i,i). The cost of such an operation is n − i + 1.
It is required to find the minimum total cost of operations that will need to be done so that the GCD of the array numbers becomes equal to 1.
Input
Each test consists of several sets of input data. The first line contains an integer t (1 <= t <= 5000) — the number of test cases. The following is a description of the input data sets.
The first line of each test case contains a single integer n (1 <= n <= 20) — the length of the array.
The second line of each test case contains n integers a₁,a₂,...,a_n (1 <= a< sub>i <= 10⁹) — array elements.
Imprint
For each test case print a single integer — the minimum total cost of operations that will need to be done so that the GCD of the array numbers becomes equal to 1.
 

Examples

ID 44036. Balance gifts

Santa Claus has N gift bags. Each bag has a weight of a1, a2, ..., < code>a_N. For a uniform load on the sleigh, Santa Claus needs the weight of all bags to be the same. To achieve this, Santa Claus with his magic staff can perform one of the following operations any number of times, possibly zero times.

• Santa Claus can choose any bag and if its weight is a multiple of two, then reduce the weight by half.
• Santa Claus can choose any bag and if it is a multiple of three, then reduce the weight by three times.

Santa Claus takes 1 second for each operation.

Find the minimum total number of seconds it takes Santa Claus to reach the same weight of all the gift bags. If there is no way to achieve the goal, print the value -1.

Examples