1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Regular Polygon (1 point)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

A regular $$$n$$$-gon is given in the plane. The length of its side is $$$\sqrt{2 - \sqrt{2}}$$$ and the length of its largest diagonal is $$$2$$$. Find all possible values of $$$n$$$. (Give the answer in the form $$$a,b,c,\dots$$$ without spaces.)

Editorial:
Direct calculations show that $$$n = 8$$$ is suitable. If $$$n$$$ is even then the largest diagonal is also a diameter of the circumscribed circle, so the only possibility is $$$n = 8$$$. If $$$n$$$ is odd then we have an isosceles triangle with side lengths $$$2$$$, $$$2$$$ and $$$\sqrt{2 - \sqrt{2}}$$$. Its smallest angle should be $$$\pi / n$$$ but it is not.
Find Number (1 point)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

Find the least natural number that has exactly $$$20$$$ natural divisors, exactly $$$4$$$ of which are odd.

Editorial:
Let this number be $$$N = 2^a p_1^{s_1} \dots p_k^{s_k}$$$, where $$$p_1$$$, $$$p_2$$$, ..., $$$p_k$$$ are different odd prime numbers. Then $$$N$$$ has $$$(a+1)(s_1+1) \dots (s_k+1)$$$ divisors and exactly $$$(s_1+1) \dots (s_k+1)$$$ odd divisors. Thus $$$(s_1+1)\dots(s_k+1) = 4$$$. Obviously the least value of $$$p_1^{s_1} \dots p_k^{s_k}$$$ in this case is $$$3 \cdot 5 = 15$$$; and no one can easily obtain $$$a = 4$$$ and $$$N = 2^4 \cdot 3 \cdot 5 = 240$$$.
Circle Radius (2 points)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

Let $$$ABCD$$$ be a square of side length $$$6$$$. Let $$$BEC$$$ be an equilateral triangle such that $$$E$$$ is outside the square. Find the radius of the circle that passes through the points $$$A$$$, $$$E$$$ and $$$D$$$.

Editorial:
Solution 1
Let $$$F$$$ be a point inside the square such that triangle $$$AFD$$$ is equilateral. Notice that $$$BE$$$ and $$$AF$$$ are parallel and have the same length, then $$$ABEF$$$ is a parallelogram and $$$EF=AB=6$$$. Finally, we have $$$FA=FE=FD=6$$$ and $$$F$$$ is the circumcenter of $$$AED$$$.
Solution 2
Since $$$BA=BE$$$ and $$$\angle ABE=150^{o}$$$, then $$$\angle BAE=15^{o}$$$ and $$$\angle EAD=75^{\circ}$$$. Analogously, $$$\angle EDA=75^{\circ}$$$. Let $$$P$$$ be the circumcenter of $$$AED$$$, we have $$$PA=PD$$$ and $$$\angle APD=2\angle AED=60^{o}$$$, therefore $$$APD$$$ is equilateral and $$$PA=PD=AD=6$$$.
Maximum Value (2 points)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

Real numbers $$$a$$$ and $$$b$$$ satisfy the equality $$$ (a + b - 1)^2 = a b + 1. $$$ What maximum value may the expression $$$a^2 + b^2$$$ take?

Editorial:
Transforming the equality, we will obtain $$$ a^2 + b^2 = 4 - (a + b - 2)^2 \le 4, $$$ and the value 4 is reached by taking $$$a = 0$$$, $$$b = 2$$$.
Eleven Segments (2 points)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

One has $$$11$$$ segments of integer lengths, the smallest length being $$$1$$$. There are no three segments such that one can build a non-degenerate triangle with them. What is the minimum possible length of the largest of the $$$11$$$ segments?

Editorial:
If the ordered lengths are $$$a_1\leq a_2 \leq \ldots \leq a_{11}$$$, then a necessary and sufficient condition is that $$$a_i+a_{i+1}\leq a_{i+2}$$$ for all $$$i\leq 9$$$. We recognize the Fibonacci sequence, and one computes easily that the minimal value for $$$a_{11}$$$ is $$$89$$$.
2018 Integers (2 points)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

$$$2018$$$ integers are written around a circle. Their sum is one. A good sequence is a sequence of consecutive (clockwise) numbers on the circle such that their sum is positive. How many good sequences are there?

Editorial:
Note that among two complementary sequences (that is, they are disjoint and their union covers all the written integers), one exactly is positive. There are $$$2018\times 2017$$$ sequences that do not cover the whole circle. Half of them are good. And, the sequence covering the whole circle is good, such that the answer is $$$\frac{2018\times 2017}{2}+1=2 035 154$$$.
Queens (2 points)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

What is the maximum number of queens that can be placed on a $$$101\times 101$$$ board so that no three queens are in the same row, column or diagonal (there are $$$402$$$ diagonals)?

Editorial:
There cannot be more than $$$202$$$ queens, since each of $$$101$$$ rows contains at most two of them. It is possible to place $$$202$$$ queens (similarly to the board of size $$$7$$$):
Seven Digit Number (2 points)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

Let $$$N$$$ be a $$$7$$$-digit number that is divisible by each of its digits. If all the digits of $$$N$$$ are different, find the sum of the digits of $$$N$$$.

Editorial:
Clearly $$$N$$$ does not contain $$$0$$$ as a digit. Since $$$N$$$ contains $$$7$$$ different digits, at least one digit is even, then $$$N$$$ is even. If $$$N$$$ contains $$$5$$$ as a digit, then $$$N$$$ is divisible by $$$5$$$ and then $$$N$$$ ends in $$$0$$$ since is even, which is a contradiction. We have to discard one more digit from {$$$1,2,3,4,6,7,8,9$$$}, therefore $$$N$$$ is divisible by $$$3$$$ and the sum of its digits is also divisible by $$$3$$$. Then we have to discard $$$1$$$, $$$4$$$ or $$$7$$$ since $$$1+2+3+4+6+7+8+9=40$$$. Anyway, $$$N$$$ is divisible by $$$9$$$ and we see that we have to discard $$$4$$$. Finally, the digits of $$$N$$$ are $$$1,2,3,6,7,8,9$$$ and the sum is $$$36$$$. One example of such $$$N$$$ is $$$9867312$$$.
All Streets (2 points)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

A tourist wants to walk through all the streets in the city and end his journey at the same point where he started. What minimum distance will the tourist have to walk? The map of the city is given in the figure; the numbers near the streets are their lengths.

Editorial:
The degrees of the vertices $$$A$$$ and $$$B$$$ in the graph are equal to $$$3$$$, which is odd (see the figure). If the tourist ends the journey where he started, then the number of times he got in a vertex is equal to the number of times he got out of it. By Euler's theorem, it follows that the tourist has to pass twice through several streets which form a way from $$$A$$$ to $$$B$$$. The shortest way from $$$A$$$ to $$$B$$$ is of length $$$240$$$, and the total length of all the streets in the city is $$$1\,120$$$. So the answer is $$$240 + 1\,120 = 1\,360$$$.
Greatest Prime Divisor (2 points)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

Consider the number $$$S = 1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3! + \cdots + 100 \cdot 100!$$$. What is the greatest prime divisor of the number $$$S+1$$$?

Editorial:
One can prove by induction that $$$1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3! + \dots + n \cdot n! = (n+1)! - 1$$$. Thus, $$$S + 1 = 101!$$$ and its greatest prime divisor is $$$101$$$.
Equilateral Triangles (2 points)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

One draws fifteen lines in the plane. What is the largest number of equilateral triangles (whose sides are on these lines) that one can generate in such a way? For example in the figure below, two equilateral triangles $$$ABC$$$ and $$$ADE$$$ are generated by four lines.

Editorial:
If one draws $$$x,y$$$ and $$$z$$$ lines according to $$$3$$$ orientations with respective angles $$$\frac{\pi}{3}$$$, with $$$x+y+z=15$$$, then the number of equilateral triangles is $$$xyz$$$, which is maximized for $$$x=y=z=5$$$. One may check easily that it is not possible to improve this bound by using more than one 'triple orientation'.
Surjective Functions (3 points)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

Let $$$M=\{1,2,3,4,5,6,7\}$$$ be a set with $$$7$$$ elements. Find the number of surjective functions $$$f:M\to M$$$ such that $$$f(f(a))\neq a$$$ and $$$f(f(f(a)))\neq a$$$ for all $$$a\in M$$$.

Note: A function $$$f:A \to B$$$ is called surjective if for each $$$b \in B$$$ there exists $$$a\in A$$$ such that $$$f(a)=b$$$.

Editorial:
A function between finite sets of the same size is surjective if and only if it is bijective. Thus, in the problem, $$$f$$$ is a permutation. The condition $$$f(f(a))\neq a$$$ implies, in particular, that $$$f(a)\neq a$$$ for all $$$a\in M$$$. If we represent the elements of $$$M$$$ as the vertices of a graph and draw an arrow from $$$a$$$ to $$$f(a)$$$, then, since $$$f$$$ is a permutation we get that the obtained graph is a union of disjoint (directed) cycles. The conditions $$$f(a)\neq a$$$, $$$f(f(a))\neq a$$$ and $$$f(f(f(a)))\neq a$$$ mean that $$$f$$$ is a $$$7$$$-cycle. There are exactly $$$7!/7 = 6! = 720$$$ distinct $$$7$$$-cycles.
Divisible by 83 (3 points)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

Consider the recurrent sequence given by $$$x_0 = 0$$$, $$$x_1 = 4$$$ and $$$x_{n+1} = 4 \cdot x_n - 3 \cdot x_{n-1}$$$ for all natural $$$n$$$. Find the minimum natural $$$n$$$ such that $$$x_n$$$ is divisible by $$$83$$$.

Editorial:
Using the general method for solving linear recurrence equations or by induction, one obtains the formula $$$x_n = 2(3^n - 1)$$$. Thus, one needs to find the smallest natural $$$k$$$ for which $$$3^k - 1$$$ is divisible by 83. By Fermat’s little theorem $$$3^{82} - 1$$$ is divisible by 83, and so $$$k$$$ should divide $$$82 = 2\cdot 41$$$. One checks that $$$3^2 - 1$$$ is not divisible by 83 but $$$$$$ 3^{41} - 1 = 3 (3^4)^{10} - 1 = 3 (81)^{10} - 1 \equiv 3 (-2)^{10} - 1 = 3071 = 37 \cdot 83. $$$$$$
Find Distance (3 points)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

Let $$$ABCD$$$ be a rectangle. A point $$$P$$$ is chosen on the segment $$$BC$$$ such that $$$\angle APD=90^o$$$. Let $$$M$$$ be the projection of $$$B$$$ on the line $$$AP$$$, $$$N$$$ be the projection of $$$C$$$ on the line $$$DP$$$ and $$$Q$$$ be the midpoint of $$$MN$$$. Given that $$$BP=32$$$ and $$$PC=18$$$, find the distance from $$$Q$$$ to the line $$$AD$$$.

Editorial:
The triangles $$$ABP$$$ and $$$PCD$$$ are similar, then $$$\frac{AB}{32}=\frac{18}{CD}$$$, since $$$AB=CD$$$, we obtain $$$AB=CD=24$$$. Triangles $$$ABM$$$ and $$$CDN$$$ are congruent, with $$$AM=NC$$$. Moreover, $$$AM$$$ and $$$NC$$$ are parallel, therefore $$$AMCN$$$ is a parallelogram and the midpoint $$$Q$$$ of $$$MN$$$ is also the midpoint of $$$AC$$$. Then, the distance from $$$Q$$$ to the line $$$AD$$$ is one half of $$$CD$$$, that is $$$12$$$.
Compute the Product (3 points)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

Let $$$a, b, c, d$$$ be real numbers such that $$$a=\sqrt{7-\sqrt{6-a}}$$$, $$$b=\sqrt{7-\sqrt{6+b}}$$$, $$$c=\sqrt{7+\sqrt{6-c}}$$$ and $$$d=\sqrt{7+\sqrt{6+d}}$$$. Compute the product $$$abcd$$$.

Editorial:
Taking twice the square in each equation, one notes that $$$a,b,-c$$$ and $$$-d$$$ are roots of the polynomial $$$x^4-14x^2-x+43$$$. The numbers $$$a,b$$$ are positive and clearly distinct, and $$$-c,-d$$$ are negative and clearly distinct. Therefore $$$a,b,-c,-d$$$ are the four distinct roots of the polynomial, hence $$$abcd=43$$$.
The Greatest Possible Value (3 points)
Contest: Mathforces: Tech Scouts Online Test 2018 (just fun and practice, unofficial, unrated)
Tags: math

Let $$$x$$$ and $$$y$$$ be positive real numbers such that $$$x^5+y^5=20xy$$$. Find the greatest possible value of $$$y^5$$$.

Editorial:
Apply AM-GM inequality to the $$$5$$$ numbers $$$x^5, \frac{y^5}{4}, \frac{y^5}{4}, \frac{y^5}{4}, \frac{y^5}{4}$$$, we get $$$y^5\leq 2^6$$$. Equality holds when $$$x=\sqrt[5]{2^4}$$$ and $$$y=\sqrt[5]{2^6}$$$. Note: The idea of the solution is to apply AM-GM to the $$$n+1$$$ numbers $$$x^5, \frac{y^5}{n}, \ldots, \frac{y^5}{n}$$$ and then find the suitable $$$n$$$ (in order to cancel $$$x$$$).
Три брата
Contest: Технокубок 2016 - Ознакомительный Раунд 1
Difficulty rating: 800

Три брата договорились о встрече. Пронумеруем братьев следующим образом: пусть старший брат имеет номер 1, средний брат имеет номер 2, а младший брат — номер 3.

Когда пришло время встречи, один из братьев опоздал. По заданным номерам двух братьев, которые пришли вовремя, вам предстоит определить номер опоздавшего брата.

Input format:
В первой строке входных данных следуют два различных целых числа a и b (1 ≤ a, b ≤ 3, a ≠ b) — номера братьев, которые пришли на встречу вовремя. Номера даны в произвольном порядке.

Output format:
Выведите единственное целое число — номер брата, который опоздал на встречу.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
3 1

Example output:
2

Editorial:
Ошибка передачи сообщения
Contest: Технокубок 2016 - Ознакомительный Раунд 1
Difficulty rating: 1400
Tags: *special, strings

В Берляндском государственном университете локальная сеть между серверами не всегда работает без ошибок. При передаче двух одинаковых сообщений подряд возможна ошибка, в результате которой эти два сообщения сливаются в одно. При таком слиянии конец первого сообщения совмещается с началом второго. Конечно, совмещение может происходить только по одинаковым символам. Длина совмещения должна быть положительным числом, меньшим длины текста сообщения.

Например, при передаче двух сообщений «abrakadabra» подряд возможно, что оно будет передано с ошибкой описанного вида, и тогда будет получено сообщение вида «abrakadabrabrakadabra» или «abrakadabrakadabra» (в первом случае совмещение произошло по одному символу, а во втором — по четырем).

По полученному сообщению t определите, возможно ли, что это результат ошибки описанного вида работы локальной сети, и если возможно, определите возможное значение s.

Не следует считать ошибкой ситуацию полного наложения друга на друга двух сообщений. К примеру, если получено сообщение «abcd», следует считать, что в нём ошибки нет. Аналогично, простое дописывание одного сообщения вслед за другим не является признаком ошибки. Например, если получено сообщение «abcabc», следует считать, что в нём ошибки нет.

Input format:
В единственной строке выходных данных следует непустая строка t, состоящая из строчных букв латинского алфавита. Длина строки t не превосходит 100 символов.

Output format:
Если сообщение t не может содержать ошибки, выведите «NO» (без кавычек) в единственную строку выходных данных.

В противном случае в первой строке выведите «YES» (без кавычек), а в следующей строке выведите строку s — возможное сообщение, которое могло привести к ошибке. Если возможных ответов несколько, разрешается вывести любой из них.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Во втором примере подходящим ответом также является строка acacaca.

Example input:
abrakadabrabrakadabra

Example output:
YES
abrakadabra

Example input:
acacacaca

Example output:
YES
acaca

Editorial:
Hit the Lottery
Contest: Codeforces Round 492 (Div. 2) [Thanks, uDebug!]
Difficulty rating: 800
Tags: dp, greedy

Allen has a LOT of money. He has $$$n$$$ dollars in the bank. For security reasons, he wants to withdraw it in cash (we will not disclose the reasons here). The denominations for dollar bills are $$$1$$$, $$$5$$$, $$$10$$$, $$$20$$$, $$$100$$$. What is the minimum number of bills Allen could receive after withdrawing his entire balance?

Input format:
The first and only line of input contains a single integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

Output format:
Output the minimum number of bills that Allen could receive.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample case, Allen can withdraw this with a $$$100$$$ dollar bill, a $$$20$$$ dollar bill, and a $$$5$$$ dollar bill. There is no way for Allen to receive $$$125$$$ dollars in one or two bills.

In the second sample case, Allen can withdraw two $$$20$$$ dollar bills and three $$$1$$$ dollar bills.

In the third sample case, Allen can withdraw $$$100000000$$$ (ten million!) $$$100$$$ dollar bills.

Example input:
125

Example output:
3

Example input:
43

Example output:
5

Editorial:
The problem is to minimize $$$x_1 + x_2 + x_3 + x_4 + x_5$$$ given that $$$x_1 + 5x_2 + 10x_3 + 20x_4 + 100x_5 = n.$$$ It is pretty simple to see that we can operate greedily: take as many $$$100$$$ as we can, then $$$20$$$, then $$$10$$$, etc.
The solutions works because each number in the sequence $$$1, 5, 10, 20, 100$$$ is a divisor of the number after it.
World Cup
Contest: Codeforces Round 492 (Div. 2) [Thanks, uDebug!]
Difficulty rating: 1300
Tags: binary search, math

Allen wants to enter a fan zone that occupies a round square and has $$$n$$$ entrances.

There already is a queue of $$$a_i$$$ people in front of the $$$i$$$-th entrance. Each entrance allows one person from its queue to enter the fan zone in one minute.

Allen uses the following strategy to enter the fan zone:

- Initially he stands in the end of the queue in front of the first entrance.
- Each minute, if he is not allowed into the fan zone during the minute (meaning he is not the first in the queue), he leaves the current queue and stands in the end of the queue of the next entrance (or the first entrance if he leaves the last entrance).

Determine the entrance through which Allen will finally enter the fan zone.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of entrances.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the number of people in queues. These numbers do not include Allen.

Output format:
Print a single integer — the number of entrance that Allen will use.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example the number of people (not including Allen) changes as follows: $$$[\textbf{2}, 3, 2, 0] \to [1, \textbf{2}, 1, 0] \to [0, 1, \textbf{0}, 0]$$$. The number in bold is the queue Alles stands in. We see that he will enter the fan zone through the third entrance.

In the second example the number of people (not including Allen) changes as follows: $$$[\textbf{10}, 10] \to [9, \textbf{9}] \to [\textbf{8}, 8] \to [7, \textbf{7}] \to [\textbf{6}, 6] \to \\ [5, \textbf{5}] \to [\textbf{4}, 4] \to [3, \textbf{3}] \to [\textbf{2}, 2] \to [1, \textbf{1}] \to [\textbf{0}, 0]$$$.

In the third example the number of people (not including Allen) changes as follows: $$$[\textbf{5}, 2, 6, 5, 7, 4] \to [4, \textbf{1}, 5, 4, 6, 3] \to [3, 0, \textbf{4}, 3, 5, 2] \to \\ [2, 0, 3, \textbf{2}, 4, 1] \to [1, 0, 2, 1, \textbf{3}, 0] \to [0, 0, 1, 0, 2, \textbf{0}]$$$.

Example input:
4
2 3 2 0

Example output:
3

Example input:
2
10 10

Example output:
1

Editorial:
For gate $$$k$$$ (where $$$1 \le k \le n$$$) we visit the gate at times $$$k, k+n, k+2n, \cdots$$$ Therefore, the earliest Allen could enter from gate $$$k$$$ is the time $$$k + tn$$$ such that $$$k + tn \ge a_k.$$$ Now, for each $$$k$$$, compute the minimal integer $$$b_k = k+tn$$$ such that $$$k+tn \ge a_k$$$. Now, find the integer $$$k$$$ with minimum $$$b_k$$$ and output $$$k$$$.
Minutes Before the New Year
Contest: Codeforces Round 611 (Div. 3)
Difficulty rating: 800
Tags: math

New Year is coming and you are excited to know how many minutes remain before the New Year. You know that currently the clock shows $$$h$$$ hours and $$$m$$$ minutes, where $$$0 \le hh < 24$$$ and $$$0 \le mm < 60$$$. We use 24-hour time format!

Your task is to find the number of minutes before the New Year. You know that New Year comes when the clock shows $$$0$$$ hours and $$$0$$$ minutes.

You have to answer $$$t$$$ independent test cases.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 1439$$$) — the number of test cases.

The following $$$t$$$ lines describe test cases. The $$$i$$$-th line contains the time as two integers $$$h$$$ and $$$m$$$ ($$$0 \le h < 24$$$, $$$0 \le m < 60$$$). It is guaranteed that this time is not a midnight, i.e. the following two conditions can't be met at the same time: $$$h=0$$$ and $$$m=0$$$. It is guaranteed that both $$$h$$$ and $$$m$$$ are given without leading zeros.

Output format:
For each test case, print the answer on it — the number of minutes before the New Year.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
5
23 55
23 0
0 1
4 20
23 59

Example output:
5
60
1439
1180
1

Editorial:
In this problem we just need to print $$$1440 - 60h - m$$$.
Candies Division
Contest: Codeforces Round 611 (Div. 3)
Difficulty rating: 900
Tags: math

Santa has $$$n$$$ candies and he wants to gift them to $$$k$$$ kids. He wants to divide as many candies as possible between all $$$k$$$ kids. Santa can't divide one candy into parts but he is allowed to not use some candies at all.

Suppose the kid who recieves the minimum number of candies has $$$a$$$ candies and the kid who recieves the maximum number of candies has $$$b$$$ candies. Then Santa will be satisfied, if the both conditions are met at the same time:

- $$$b - a \le 1$$$ (it means $$$b = a$$$ or $$$b = a + 1$$$);
- the number of kids who has $$$a+1$$$ candies (note that $$$a+1$$$ not necessarily equals $$$b$$$) does not exceed $$$\lfloor\frac{k}{2}\rfloor$$$ (less than or equal to $$$\lfloor\frac{k}{2}\rfloor$$$).

$$$\lfloor\frac{k}{2}\rfloor$$$ is $$$k$$$ divided by $$$2$$$ and rounded down to the nearest integer. For example, if $$$k=5$$$ then $$$\lfloor\frac{k}{2}\rfloor=\lfloor\frac{5}{2}\rfloor=2$$$.

Your task is to find the maximum number of candies Santa can give to kids so that he will be satisfied.

You have to answer $$$t$$$ independent test cases.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — the number of test cases.

The next $$$t$$$ lines describe test cases. The $$$i$$$-th test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 10^9$$$) — the number of candies and the number of kids.

Output format:
For each test case print the answer on it — the maximum number of candies Santa can give to kids so that he will be satisfied.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Santa can give $$$3$$$ and $$$2$$$ candies to kids. There $$$a=2, b=3,a+1=3$$$.

In the second test case, Santa can give $$$5, 5, 4$$$ and $$$4$$$ candies. There $$$a=4,b=5,a+1=5$$$. The answer cannot be greater because then the number of kids with $$$5$$$ candies will be $$$3$$$.

In the third test case, Santa can distribute candies in the following way: $$$[1, 2, 2, 1, 1, 2, 1]$$$. There $$$a=1,b=2,a+1=2$$$. He cannot distribute two remaining candies in a way to be satisfied.

In the fourth test case, Santa can distribute candies in the following way: $$$[3, 3]$$$. There $$$a=3, b=3, a+1=4$$$. Santa distributed all $$$6$$$ candies.

Example input:
5
5 2
19 4
12 7
6 2
100000 50010

Example output:
5
18
10
6
75015

Editorial:
Firstly, we can notice that we always can distribute $$$n - n \% k$$$ (where $$$\%$$$ is the modulo operation) candies between kids. In this case $$$a=\lfloor\frac{n}{k}\rfloor$$$ and the answer is at least $$$ak$$$. And then we can add the value $$$min(n \% k, \lfloor\frac{k}{2}\rfloor)$$$ to the answer. Why? Because there is only $$$n \% k$$$ candies remain and the maximum number of kids to whom we can give one more candy is $$$\lfloor\frac{k}{2}\rfloor$$$.