JUST ACM Problem Solving Competition for PSUT
A. Hmsh's calculator
time limit per test
1 s.
memory limit per test
256 MB
input
standard input
output
standard output

Ayham forgot his calculator before the exam, so he borrowed Hmsh's calculator from Qawasmeh. During the exam, he discovered that whenever he presses the add button, the calculator subtracts instead of adding.

Ayham needs to add two numbers $$$a$$$ and $$$b$$$ using the calculator. Help him to find the answer.

Input

The first and only line contains two integers $$$a$$$ and $$$b$$$ $$$(1 \le a, b \le 100)$$$.

Output

Output the result of adding the two numbers using Hmsh's calculator.

Examples
Input
5 3
Output
2
Input
1 1
Output
0
Input
1 2
Output
-1
B. Yahya's Graduation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Basheer missed the graduation notebook ceremony for the Computer Science batch of 2021. Consequently, he didn't have the chance to write a message in Yahya's notebook.To make up for this, Basheer and Yahya have arranged a meeting at a local cafe. However, Yahya has a very strict and detailed schedule. Yahya has provided Basheer with the exact time he plans to leave the cafe.Given Basheer's arrival time $$$T_b$$$ and Yahya's departure time $$$T_y$$$, your task is to determine if Basheer will arrive at the cafe before or exactly at the time Yahya leaves. If Basheer arrives even one minute after Yahya leaves, he will miss his chance.

Input

The first line contains two integers $$$H_b$$$ and $$$M_b$$$ ($$$0 \le H_b \lt 24, 0 \le M_b \lt 60$$$) — the hour and minute of Basheer's arrival.

The second line contains two integers $$$H_y$$$ and $$$M_y$$$ ($$$0 \le H_y \lt 24, 0 \le M_y \lt 60$$$) — the hour and minute of Yahya's departure.

You can assume that Basheer's arrival time and Yahya's departure time are on the same day.

Output

Print "YES" (without quotes) if Basheer arrives at or before Yahya's departure time. Otherwise, print "NO".

Examples
Input
14 30 15 00
Output
YES
Input
10 15 10 10
Output
NO

C. The OG 3ATATEET
time limit per test
1 s.
memory limit per test
256 MB
input
standard input
output
standard output

$$$3AT3EET$$$ has a strange hobby: he loves shooing away pigeons. Today, he decided to practice his hobby in an infinite tower.

His friend, $$$The\_OG\_Kashish$$$, resides on the $$$k-th$$$ floor of this tower. $$$3AT3EET$$$ starts at the ground floor (floor $$$0$$$) and wants to reach $$$The\_OG\_Kashish$$$'s floor to join him in shooing the pigeons.

The tower is equipped with a very peculiar elevator. It has only two buttons:

$$$UP$$$: Moves the elevator exactly $$$x$$$ floors up (adds $$$x$$$ to the current floor).

$$$DOWN$$$: Moves the elevator exactly $$$1$$$ floor down (subtracts $$$1$$$ from the current floor).

Note that since the tower is infinite, the floor number can go arbitrarily high, but it cannot go below zero.

Your task is to determine the minimum number of button presses required for $$$3AT3EET$$$ to go from floor $$$0$$$ to floor $$$k$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line of each test case contains two integers $$$x$$$ and $$$k$$$ ($$$1 \le x, k \le 10^9$$$) — the number of floors the elevator moves up, and the target floor where $$$The\_OG\_Kashish$$$ lives.

Output

For each test case, print a single integer — the minimum number of button presses required to reach floor $$$k$$$.

Example
Input
4
5 20
5 22
3 11
3 1000000000
Output
4
8
5
333333336
D. Saleem The Driver
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Malabeh loves putting numbers into boxes. He puts $$$1$$$ in the first box, $$$2$$$ in the second, and so on, until the $$$n$$$-th box contains the number $$$n$$$.

One day, he asked his friend, the professional driver Saleem, to deliver all the boxes to the land of Samar.

But Ayham the trickster stole one box on the way.

Saleem only knows the sum of the numbers after the theft. Note that you don't know $$$n$$$.

Help Saleem to find the number on the stolen box.

Input

The only line of each test case contains a single integer $$$s$$$ ($$$1 \le s \le 10^{12}$$$) — the sum of the numbers on the remaining boxes after the theft.

Output

print a single integer — the number on the stolen box.

It is guaranteed that for each test case, there is exactly one unique answer.

Examples
Input
4
Output
2
Input
24
Output
4
Input
17
Output
4
Note

In the first testcase, the initial boxes were $$$1, 2$$$, and $$$3$$$. Ayham stole the box with the number $$$2$$$, so the remaining boxes are $$$1$$$ and $$$3$$$, which sum to $$$4$$$.

In the second testcase, the initial boxes were $$$1, 2, 3, 4, 5, 6$$$, and $$$7$$$. Ayham stole the box with the number $$$4$$$, so the remaining boxes are $$$1, 2, 3, 5, 6,$$$ and $$$7$$$, which sum to $$$24$$$.

E. Not a cards game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob play a game.

Alice has $$$n$$$ cards and Bob has $$$n$$$ cards. Each card has an integer power.

You are given two arrays $$$a_1, a_2, \dots, a_n$$$ and $$$b_1, b_2, \dots, b_n$$$, where $$$a_j$$$ is the power of Alice's $$$j$$$-th card and $$$b_i$$$ is the power of Bob's $$$i$$$-th card.

The game consists of $$$n$$$ rounds. In round $$$i$$$ $$$(1 \le i \le n)$$$, Bob plays his $$$i$$$-th card (with power $$$b_i$$$). Then Alice chooses any one of her remaining (unused) cards and plays it against Bob's card. If the power of Alice's chosen card is strictly greater than $$$b_i$$$, Alice wins this round.

Each Alice card can be used at most once.

Find the maximum number of rounds Alice can win if she plays optimally.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases.

Each test case consists of three lines:

  • The first line contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$.
  • The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$.
  • The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ $$$(1 \le b_i \le 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print one integer — the maximum number of rounds Alice can win.

Example
Input
4
3
7 1 3
9 2 5
2
6 2
6 6
5
8 9 2 1 7
4 5 3 1 6
1
7
6
Output
2
0
4
1

F. Three Cuts
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of $$$n$$$ integers, where $$$n$$$ is even. You can perform the following operation until the array becomes empty:

Choose indices $$$i$$$,$$$j$$$ such that $$$i \ne j$$$, add $$$\lceil (a_i + a_j)/3 \rceil$$$ to your score, and remove $$$a_i$$$ and $$$a_j$$$ from the array.

Find the maximum score you can obtain.

Here, $$$\lceil x \rceil$$$ (the ceiling of $$$x$$$) is the smallest integer greater than or equal to $$$x$$$. For example, $$$\lceil 2.1 \rceil = 3$$$, $$$\lceil 5 \rceil = 5$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases. The description of the test cases follows.

Each test case consists of two lines.

The first line contains a single even integer $$$n$$$ $$$(2 \le n \le 2\cdot10^5)$$$ — the size of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(0 \le a_i \le 10^9)$$$ — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output

For each test case print a single integer — the maximum score obtainable.

Example
Input
3
4
1 1 1 1
2
5 6
6
1 0 2 2 1 1
Output
2
4
4

G. Palindromicable String
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ of length $$$n$$$ and an integer $$$k$$$.

Determine whether it is possible to remove exactly one substring of length $$$k$$$ from $$$s$$$ such that the remaining string is a palindrome.

_________________________________

A substring of a string $$$s$$$ is a continuous segment of characters in $$$s$$$, $$$s[l..r]$$$ $$$(1 \le l \le r \le n)$$$. For example, $$$"code"$$$ is a substring of $$$"codeforces"$$$, while $$$"cfs"$$$ is not.

A palindrome is a string that reads the same from left to right as from right to left. For example, $$$abacaba$$$, $$$aaaa$$$, $$$abba$$$, palindromes while $$$abc$$$ , $$$abbb$$$ is not.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t (1 \le t \le 10^4)$$$.The description of the test cases follows.

The first line of each test case contain two integers $$$n,k (1 \le n \le 10^5) (1 \le k \lt min(n,100))$$$ the size of the string $$$s$$$ and the size of the substring to remove.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters.

Its guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case Print "1" if it is possible to remove exactly one substring of length $$$k$$$ such that the remaining string is a palindrome. Otherwise, print "0".

Example
Input
4
4 2
aaaa
5 4
abcde
6 2
abccbe
3 1
aba
Output
1
1
0
1

H. Can you count ?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer array $$$a$$$ of length $$$n$$$ and an integer $$$p$$$.

Count the number of pairs of indices $$$(i,j)$$$ such that $$$1 \le i \lt j \le n$$$, and $$$$$$ \frac{a_i^2 + a_j^2}{a_i + a_j} = p. $$$$$$

Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases.

Each test case consists of:

- the first line of each test case contains two integers $$$n$$$ and $$$p$$$ $$$(2 \le n \le 2 \cdot 10^5,\ 1 \le p \le 10^9)$$$.

- the second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

Print a single integer — the number of pairs $$$(i,j)$$$ satisfying the condition.

Examples
Input
3
5 3
3 6 1 2 3
3 2
1 2 3
5 100
1 15 15 15 15
Output
1
0
0
Input
4
2 5
5 5
3 1
1 1 1000000000
5 7
7 7 1000000000 9 39
10 42
42 42 1000000000 46 9 23 37 47 34 5
Output
1
1
1
1

I. Bitonic Arrays
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$.

In one operation, you choose an index $$$i$$$ $$$(1 \le i \le n)$$$ and do $$$a_i := a_i + 1$$$.

An array $$$b$$$ of length $$$n$$$ is called bitonic if there exists an index $$$p$$$ $$$(1 \le p \le n)$$$ such that:

  • $$$b_1 \le b_2 \le \dots \le b_p$$$,
  • $$$b_p \ge b_{p+1} \ge \dots \ge b_n$$$.
(Equality is allowed, i.e. the array is non-decreasing up to $$$p$$$ and non-increasing after $$$p$$$.)

Find the minimum number of operations required to make the array bitonic.

Input

The first line contains one integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases.

For each test case:

  • The first line contains one integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — the length of the array.
  • The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(0 \le a_i \le 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, print one integer — the minimum number of operations required to make the array bitonic.

Example
Input
6
5
1 2 3 2 1
3
1 0 1
2
5 15
6
5 0 7 15 3 2
3
3 2 1
7
1 2 3 1 3 2 1
Output
0
1
0
5
0
2