EPT Solving Cup 5.0 공식 경연대회
A. Squid Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the Squid Game competition, each game requires different abilities to succeed. Unfortunately, you are player '$$$0$$$' and you have no abilities, and you must choose your teammates wisely to maximize your chances of winning. Each teammate will bring a set of abilities to the table, and your goal is to ensure that every one of your teammates has at least one ability required for a game.

For each game, you are given a number $$$x$$$ representing the abilities required for this game. The task is to determine how many people among $$$n$$$ players can join your team for that game, and whether it is guaranteed that your team will win.

Your team is guaranteed to win a game if, for every ability required by the game, at least one of your teammates possesses that ability.

A set of abilities isrepresented by a number . A number $$$a$$$ means a player has certain abilities, where the $$$j^{th}$$$ bit of $$$a$$$ in its binary representation is $$$1$$$ if the player masters the $$$j^{th}$$$ ability and $$$0$$$ otherwise.

Every player has at most 6 different abilities.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 2.10^5$$$), the number of players numbered from $$$1$$$ to $$$n$$$ and the number of games.

The second line contains $$$n$$$ integers $$$a_{1},a_{2},...,a_{n-1},a_{n}$$$ ($$$0 \leq a_{i} \leq 2^{20}-2^{14}$$$), where $$$a_{i}$$$ is the set of abilities of player $$$i$$$.

The next q line contains an integer $$$x$$$ ($$$0 \leq x \leq 2^{20}$$$), representing the abilities required for this game.

It's guaranteed that every player has at most 6 different abilities.

Output

For each game, print two integers:

  • The number of players that can join you for the game(have at least one of the abilities required for the game).
  • $$$1$$$ if it's guaranteed to win (for each required ability there is at least one of your teammates that has that ability) or $$$0$$$ otherwise.
Examples
Input
7 2
0 1 2 3 2 1 0
1
3
Output
3 1
5 1
Input
8 2
1 2 3 4 5 6 7 2
2
5
Output
5 1
6 1

B. Red Light Green Light
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Two players, Player 001 and Player 002, are trapped in a mysterious tree-shaped battleground. Their objective is to visit the least number of nodes—because in this game, the more steps you take, the closer you are to elimination.

The game is controlled by the Squid Game Dummy, who gives each second a Green Light to move and a Red Light to stop. This ensures that both players move simultaneously when the Green Light is given. Keep in mind that both players will aim to play optimally.

Game Rules

  • Each second, a player must move one step toward the closest unvisited node they can reach. They continue moving toward it until they arrive, then proceed to the next closest unvisited node. If multiple nodes are equidistant, the player may choose any of them.
  • No Backtracking: A player can not enter a node that the other player has already visited, but he can visit his own visited nodes multiple times.
  • Collision Penalty: If both players land on the same node at the same time, they must immediately retreat and continue visiting new nodes separately, and this node can not be visited any more.
  • Waiting Rule: If a player has no available moves, they must wait until the other player finishes their movements.
  • Losing Condition: The player who visits more nodes loses the game.

The Front Man's Twist

The Front Man noticed that with an even number of nodes, the game often ends in a tie—which he finds boring. To ensure a decisive outcome, he made sure that the number of nodes in the tree is always odd.

Input
  • $$$1 \leq t \leq 10000$$$ — the number of test cases.
  • $$$3 \leq n \leq 3 \times 10^5$$$ — the number of nodes in the tree, and $$$n$$$ is always odd.
  • $$$1 \leq q \leq 3 \times 10^5$$$ — the number of queries per test case.
  • It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases does not exceed $$$3 \times 10^5$$$.
  • The first line contains an integer $$$t$$$, the number of test cases.
  • For each test case:
    • The first line contains two integers $$$n$$$ and $$$q$$$, the number of nodes in the tree and the number of queries.
    • The next $$$n-1$$$ lines contain two integers $$$u$$$ and $$$v$$$, indicating a road between node $$$u$$$ and node $$$v$$$.
    • The next $$$q$$$ lines contain two integers $$$x$$$ and $$$y$$$, the starting positions of the two players, with $$$x \neq y$$$.
Output
  • For each query, output "001" if Player 001 wins.
  • Otherwise, output "002" if Player 002 wins.
  • In case of a tie (both players visit the same number of nodes), output "Remake!"
Example
Input
2
3 1
1 2
2 3
3 2
5 2
1 2
2 3
3 4
4 5
1 4
1 5
Output
001
002
Remake!
Note

This is an example of a gameplay. Let's use a black dot to represent each player's current position. Each player has their own black dot. Query 1:

test case 2 query 1.
At the start (t=1), Player 2 is at Node 4, and Player 1 is at Node 1. Player 2 can choose between Node 5 or Node 3 but decides to visit Node 5 first. Player 1, on the other hand, has only one option: Node 2, so they must visit Node 2.

At time t=2: Player 2 must move toward the closest unvisited node, so they start walking toward Node 3. Player 1 also moves toward the closest unvisited node, which is Node 3.

At time t=3: All nodes have been colored and visited by at least one player, so the game ends.

Query 2:

test case 2 query 2.

C. Dalgona Challenge
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the Dalgona Challenge from Squid Game, players must carefully carve out a shape from a honeycomb candy using a needle. The Masked Guards have designed a new version of this challenge using laser-cut patterns on a circular honeycomb.

You are g iven a circular honeycomb with $$$n$$$ points along its boundary. The guards use laser cutters to draw a straight line between every pair of these points. That is, for every possible pair of distinct points, a straight laser cut is made, linking each point with every other point. These laser cuts create a complex pattern of intersecting lines that divide the honeycomb into multiple regions.

Your task is to determine the maximum number of regions the honeycomb can be divided into when all possible laser cuts are made.

Input

The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^{5} $$$).

Each test case contains :

A single integer $$$n$$$ ($$$0 \leq n \leq 10^{5}$$$), representing the number of points.

Output

A single integer, the maximum number of regions formed in the honeycomb.

Example
Input
3
1
4
6
Output
1
8
31
Note

In the first two testcases, the result is obvious.

In the third testcase, it can be proven that the maximum number of regions obtained after placing 6 points in the circle optimally is $$$31$$$

test case 3 .

D. The Marble Duel
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In one of the Squid Game challenges, Seong Gi-hun (Player 456) and Oh Il-nam (Player 001) face off in a game where they start with $$$n$$$ bags of marbles. Each bag has $$$a_{i}$$$ marbles. The rules are simple:

  • On each player's turn, they can choose any bag among the n ones.
  • They can remove exactly 1, x, or y marbles from that bag.
  • The game continues in turns until one player cannot make a valid move.
  • The player who cannot make a valid move loses.
Your task is to determine who will win the game, assuming both players play optimally. The game starts with Seong Gi-hun (Player 456) taking the first turn.
Input

In the first line, there is a single integer $$$t$$$ ($$$1 \leq t \leq 2.10^5$$$), representing the number of testcases.

In each testcase, there are three lines:

  • In the first line, there is a single integer $$$n$$$ ($$$1 \leq n \leq 2.10^5$$$), representing the number of bags of marbles.
  • In the second line, there are two integers $$$x$$$ and $$$y$$$ ($$$3 \leq x \lt y \leq 10^{18}$$$), representing the number of marbles each player can remove.
  • In the third line, there are $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1 \leq a_i \leq 10^{18}$$$), representing the number of marbles each bag has.
It's guaranteed that $$$x$$$ is odd and the sum of $$$n$$$ over all testcases is less than $$$2.10^{5}$$$
Output

Output "456" if Seong Gi-hun will win the game, or "001" if Oh Il-nam will win, assuming both players play optimally.

Example
Input
4
1
3 4
2
1
3 4
4
2
3 4
1000000000000000000 1000000000000000000
2
3 4
2 4
Output
001
456
001
456

E. The Deadly Escape
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

In the Squid Game, players find themselves trapped in a massive, deadly tree-like structure with $$$n$$$ platforms (nodes). Each platform has a danger level $$$a_i$$$, representing its instability. Platforms are connected by rope bridges with different weight values $$$w_i$$$, determining the difficulty of crossing between them. Players can jump from one platform to any platform in its subtree, but each jump comes at a cost:

jump's cost $$$=a_y$$$ $$$($$$weight of the path from $$$x$$$ to $$$y$$$$$$)$$$

where $$$x$$$ is the current platform and $$$y$$$ is the destination.

The goal for each player, starting from any platform, is to find the safest escape route to a leaf platform, where the total jumping cost is minimized. However, the root platform (1) is cursed and can never be a leaf, even if it has only one connection!

Can you find the optimal escape path for each platform before the deadly Squid Game masters close in?

Input

The first line of input contains an integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$), the number of nodes in the tree.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^6 \leq a_i \leq 10^6$$$),representing each platform danger level.

Next $$$n - 1$$$ lines contain two space-separated integers $$$u_i$$$ , $$$v_i$$$ and $$$w_i$$$ ($$$1 \leq u_i, v_i \leq n , -10^6 \leq w_i \leq 10^6$$$) describing a rope bridge between platforms $$$u_i$$$ and $$$v_i$$$ given its weight.

Output

Output $$$n$$$ space-separated integers, the $$$i$$$-th of which denotes the minimum cost of a path from platform $$$i$$$ to reach any leaf.

Examples
Input
3
2 -1 1
1 2 3
2 3 -2
Output
-5 -2 0 
Input
5
3 -1 2 -2 -4
1 2 3
1 3 -1
3 4 -2
3 5 1
Output
-6 0 -4 0 0 
Input
7
1 -3 2 -4 5 -3 -1
1 2 -1
1 3 -2
2 4 2
2 5 -1
3 6 -2
3 7 1
Output
-10 -8 -1 0 0 0 0 

F. The Glass Bridge Challenge
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the Squid Game, players must cross a dangerous glass bridge consisting of $$$n$$$ planks. Each plank has a danger value $$$a_{i}$$$ , representing how unstable it is. Players must strategically place $$$k$$$ safe planks on the bridge to divide it into $$$k+1$$$ segments, making their path safer.

The survival cost of a segment is determined by the number of divisors ($$$\tau $$$) of the product of all danger values in that segment. The total survival cost is the sum of the survival costs of all segments.

For example, for a bridge $$$[20,1,1,1] $$$ and $$$k=1$$$, an optimal way is to divide the bridge into two segments: $$$[20]$$$ and $$$[1,1,1] $$$, and the total cost $$$=6+1=7$$$.

Your task is to strategically place the $$$k$$$ dividers to minimize the total survival cost, ensuring the safest possible route across the bridge. Can you survive the Glass Bridge Challenge and reach the other side?

Input

The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 500 $$$).

Each test case contains two lines :

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^{3} , 1 \leq k \leq min(100,n-1) $$$), representing the number of the planks and the number of safe planks .

The second line contains $$$n$$$ integers $$$a_1,a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^{6})$$$ representing the danger value of the planks.

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

Output

Print one integer, the minimum total survival cost after optimally placing the safe planks.

It's guaranteed that the minimum total survival cost after optimally placing the safe planks does not exceed $$$10^{18}$$$.

Example
Input
5
5 1
20 1 1 1 1
5 2
4 6 8 2 3
4 1
2 3 4 5
3 1
4 6 8
5 2
2 12 9 24 8
Output
7
15
10
12
25
Note

In the second testcase, a best way is to divide the bridge into 3 segments $$$[4,6],[8,2],[3] $$$ so the total cost $$$=8+5+2=15$$$

G. The Totient Challenge
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In this challenge, $$$n$$$ players are arranged in a line with positions numbered from $$$1$$$ to $$$n$$$. The goal of the challenge is simple: only a few players will survive, and the rest will be eliminated based on their position and a mathematical property known as Euler's Totient Function.

After the players are arranged, a guard will go through each position and determine whether the player in that position should be eliminated or not. The decision to eliminate a player depends on a mathematical condition involving Euler's Totient Function, $$$\varphi(k)$$$, which is defined as the number of integers from $$$1$$$ to $$$k$$$ that are coprime with $$$k$$$. To make the decision, the guard will check each position $$$k$$$ $$$(1 \leq k \leq n)$$$ and ask, does $$$\varphi(k)$$$ divide $$$k$$$? If yes, the player survives; otherwise, the player in that position will be eliminated.

Your task is to determine how many players will survive.

Input

A single integer $$$n$$$ $$$(1 \leq n \leq 10^{18} )$$$ — number of players.

Output

Output a single integer representing the number of survivors.

Examples
Input
6
Output
4
Input
1000000
Output
130
Note

Euler's totient function, denoted as $$$ \varphi(n) $$$, counts the number of positive integers from $$$ 1 $$$ to $$$ n $$$ that are coprime to $$$ n $$$, meaning they do not share any common divisor with $$$ n $$$ other than $$$ 1 $$$.

The function satisfies the following formula for any positive integer $$$ n $$$ with prime factorization:

$$$$$$ n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k} $$$$$$

where $$$ p_1, p_2, \dots, p_k $$$ are distinct prime numbers. The totient function is given by:

$$$$$$ \varphi(n) = n \left( 1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) \dots \left( 1 - \frac{1}{p_k} \right) $$$$$$

For a prime number $$$ p $$$, we have:

$$$$$$ \varphi(p) = p - 1 $$$$$$

since all numbers less than $$$p $$$ are coprime to it.

test case 1

  • $$$\varphi(1)=1$$$ because only the number $$$1$$$ is coprime with itself.
  • $$$\varphi(2)=1$$$ because only the number $$$1$$$ is coprime to $$$2$$$.
  • $$$\varphi(3)=2$$$ because only the numbers $$$1$$$ and $$$2$$$ are coprime to $$$3$$$.
  • $$$\varphi(4)=2$$$ because only the numbers $$$1$$$ and $$$3$$$ are coprime to $$$3$$$.
  • $$$\varphi(5)=4$$$ because only the numbers $$$1$$$ and $$$2$$$ are coprime to $$$3$$$.
  • $$$\varphi(6)=2$$$ because only the numbers $$$1$$$ and $$$5$$$ are coprime to $$$6$$$.
So only players in positions $$$1,2,4$$$ and $$$6$$$ are the survivors

H. The Revolving Death Clock
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In one of the Squid Game challenges, a Revolving Death Clock determines the fate of the players. The clock consists of two circular gears: a smaller gear (the Death Gear) rotates around a larger circular base (the Clock Gear).

The Death Gear starts at a specific point on the Clock Gear and rotates around it. Your task is to determine the minimum number of full rotations the Death Gear completes before returning to its starting position relative to the Clock Gear. You are given two circles:

  • The Clock Gear with diameter $$$D_{1}$$$
  • The Death Gear with diameter $$$D_{2}$$$
The Death Gear rolls without slipping along the edge of the Clock Gear. Determine the minimum integer number of complete rotations the Death Gear makes around itself before returning to its initial position.
This is an example of how the gear rotates.
Input

The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^{6} $$$)

Each test case contains :

Two integers $$$D_{1}$$$ and $$$D_{2}$$$ ($$$1 \leq D_{2} \leq D_{1} \leq 10^{9} $$$), representing the diameters of the Clock Gear and the Death Gear, respectively.

Output

For each test case, output a single integer, the minimum integer number of complete rotations the Death Gear makes around itself before returning to its starting position.

Example
Input
2
1 1
3 1
Output
2
4
Note

The first test case: here.

I. The Binary Escape Challenge
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In this challenge, you are tasked with helping the players navigate through a series of binary gates. The guards have set up a system where each gate is either "open" (denoted by $$$1$$$) or "closed" (denoted by $$$0$$$). The challenge is to escape through the gates by ensuring you have a segment of open gates large enough to slip through without being caught.

You are given two integers,$$$n$$$ — the total number of gates (binary sequence length)and $$$l$$$ — the minimum number of consecutive open gates (i.e., $$$1s$$$) required to successfully escape.

Your task is to determine how many binary sequences of length $$$n$$$ contain at least one contiguous subsegment of length $$$l$$$ consisting only of $$$1s$$$. The sequence can contain any combination of $$$0s$$$ and $$$1s$$$, but to successfully escape, there must be a subsegment of $$$l$$$ consecutive $$$1s$$$ somewhere in the sequence.

Since the number of such sequences can be quite large, output the result modulo $$$10^9+7$$$.

Input

A single line containing two integers $$$n$$$ $$$(1 \leq n \leq 10^9)$$$ and $$$l$$$ $$$(1 \leq l \leq 100)$$$ respectively representing the total number of gates and the minimum number of consecutive open gates required to successfully escape.

Output

Output a single integer — the number of valid binary sequences of length $$$n$$$ that satisfy the condition, modulo $$$10^9+7$$$.

Example
Input
3 2
Output
3
Note

In the first test, all possible sequences of gates are :

$$$000,001,010,011,100,101,110,111$$$.

The only valid ones are :

$$$011,110,111$$$.

So the answer is 3.

J. The Guards' Challenge - Easy Version
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the easy version, guards can use the operations only once.

In the next round of the Squid Game, players must be arranged by their numbers from $$$1$$$ to $$$n$$$. Guards must rearrange the players that initially are shuffled in a random order. Time is crucial, so they have to minimize the time needed to do that.

A guard can do the following operations :

  • Choose an integer $$$k$$$.
  • Divide the players into $$$k$$$ segments.
  • Shuffle the players while maintaining their relative order. This means that, for example, if the segments contain the players $$$[3,1,5]$$$ and $$$[2,6,4,7]$$$, after shuffling, the players must still appear in that order, meaning that these segments $$$[3,2,6,1,5,4,7]$$$ and $$$[3,1,2,6,5,4,7]$$$ are correct because $$$3,1$$$ and $$$5$$$ appeared in the same order as the segment $$$[3,1,5]$$$ and $$$2,4,6$$$ and $$$7$$$ appeared in the same order as the segment $$$[2,6,4,7]$$$, but $$$[1,2,6,3,5,4]$$$ is not correct because $$$3$$$ appeared after $$$1$$$, not in the same order as $$$[3,1,5]$$$.
Time needed for the operation is equal to $$$k$$$, the number of segments.

The goal of the guards is to rearrange the players into the correct order $$$1,2,...,n$$$, using these operations only once, while minimizing the total time. The guards can perform these operations infinitely, but they must be strategic in choosing the number of segments each time because the more segments they use, the longer it takes.

Input

The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 10^5)$$$ — the number of players.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ $$$(1 \le a_i \le n)$$$ — the initial permutation of players.

Output

Print a single integer, the minimum time needed to rearrange the players.

Examples
Input
5
5 4 2 3 1
Output
4
Input
5
3 4 5 1 2
Output
2
Input
6
6 5 4 3 2 1
Output
6
Input
5
1 2 3 4 5
Output
0
Note

In the first test, you can divide the players into $$$4$$$ segments $$$[5]$$$,$$$[4]$$$,$$$[2,3]$$$ and $$$[1]$$$ and shuffle them into $$$[1,2,3,4,5]$$$. So the answer is $$$4$$$.

In the second test, you can divide the players into $$$2$$$ segments $$$[3,4,5]$$$ and $$$[1,2]$$$ and shuffle them into $$$[1,2,3,4,5]$$$. So the answer is $$$2$$$.

In the third test, you can divide the players into $$$6$$$ segments $$$[6]$$$,$$$[5]$$$,$$$[4]$$$,$$$[3]$$$,$$$[2]$$$ and $$$[1]$$$ and shuffle them into $$$[1,2,3,4,5,6]$$$. So the answer is $$$6$$$.

K. The Guards' Challenge - Hard Version
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the hard version, guards can use the operations as many times as needed

In the next round of the Squid Game, players must be arranged by their numbers from $$$1$$$ to $$$n$$$. Guards must rearrange the players that initially are shuffled in a random order. Time is crucial, so they have to minimize the time needed to do that.

A guard can do the following operations :

  • Choose an integer $$$k$$$.
  • Divide the players into $$$k$$$ segments.
  • Shuffle the players while maintaining their relative order. This means that, for example, if the segments contain the players $$$[3,1,5]$$$ and $$$[2,6,4,7]$$$, after shuffling, the players must still appear in that order, meaning that these segments $$$[3,2,6,1,5,4,7]$$$ and $$$[3,1,2,6,5,4,7]$$$ are correct because $$$3,1$$$ and $$$5$$$ appeared in the same order as the segment $$$[3,1,5]$$$ and $$$2,4,6$$$ and $$$7$$$ appeared in the same order as the segment $$$[2,6,4,7]$$$, but $$$[1,2,6,3,5,4]$$$ is not correct because $$$3$$$ appeared after $$$1$$$, not in the same order as $$$[3,1,5]$$$.
Time needed for the operation is equal to $$$k$$$, the number of segments.

The goal of the guards is to rearrange the players into the correct order $$$1,2,...,n$$$, using these operations as many times as needed, while minimizing the total time. The guards can perform these operations infinitely, but they must be strategic in choosing the number of segments each time because the more segments they use, the longer it takes.

Input

The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 10^5)$$$ — the number of players.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ $$$(1 \le a_i \le n)$$$ — the initial permutation of players.

Output

Print a single integer, the minimum time needed to rearrange the players.

Examples
Input
5
5 4 2 3 1
Output
4
Input
5
3 4 5 1 2
Output
2
Input
6
6 5 4 3 2 1
Output
5
Input
5
1 2 3 4 5
Output
0
Note

In the first test, you can divide the players into $$$4$$$ segments $$$[5]$$$,$$$[4]$$$,$$$[2,3]$$$ and $$$[1]$$$ and shuffle them into $$$[1,2,3,4,5]$$$. So the answer is $$$4$$$.

In the second test, you can divide the players into $$$2$$$ segments $$$[3,4,5]$$$ and $$$[1,2]$$$ and shuffle them into $$$[1,2,3,4,5]$$$. So the answer is $$$2$$$.

In the third test, you can divide the players into $$$2$$$ segments $$$[6,5,4]$$$ and $$$[3,2,1]$$$ and shuffle them into $$$[3,6,2,5,1,4]$$$.Then divide the players into $$$3$$$ segments $$$[3,6]$$$,$$$[2,5]$$$ and $$$[1,4]$$$and shuffle them into $$$[1,2,3,4,5,6]$$$. So the answer is $$$2+3=5$$$.

L. Player 001
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The enigmatic owner of the Squid Games is searching for a new Front Man to take over his position and become Player 001. However, before he entrusts you with this role, he must test your intelligence.

Your first task seems simple:

Given an integer $$$ 1 \leq N \leq 10^{17} $$$, compute the sum of the digits of all numbers $$$ i $$$ for $$$ 1 \leq i \leq N $$$. That is, your answer should be:

$$$ \sum_{i=1}^{N} \text{sum_of_digits}(i) $$$

However, the owner finds this challenge too easy. To truly prove your worth, you must answer $$$ t $$$ consecutive test cases correctly.

Can you pass the test and claim the title of Player 001?

Input

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

Each of the next $$$ t $$$ lines contains a single integer $$$ N $$$ $$$(1 \leq N \leq 10^{17})$$$.

Output

For each test case, output a single integer — the sum of the digits of all numbers $$$ i $$$ for $$$ 1 \leq i \leq N $$$.

Print each answer on a new line.

Example
Input
4
12
10
1
1254
Output
51
46
1
16125
Note

Example of Sum of Digits of a Number: sum_digits(10) = 1 + 0 = 1 sum_digits(123) = 1 + 2 + 3 = 6 And so on.

Explanation of a Test Case: Let's denote the function sum_of_digits as s. For Test Case 2, we calculate the sum of digits for all integers $$$i$$$ where $$$1 \leq i \leq 10$$$: $$$s(1) + s(2) + s(3) + s(4) + s(5) + s(6) + s(7) + s(8) + s(9) + s(10)= 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + (1 + 0)= 46$$$

M. The Maximum MEX Challenge
time limit per test
7 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In this round of the Squid Game, the players are presented with $$$n$$$ locked vaults, each containing a hidden number. The guards provide an interval $$$[l, r]$$$ for each vault, indicating that the number inside must be chosen from this range.

Each player must select exactly one number from each interval, forming a sequence of $$$n$$$ numbers. The objective is to maximize the MEX of this sequence.

The mex of a sequence is the smallest non-negative integer that does not appear in the sequence. For example:

  • The mex of $$$[0, 1, 2]$$$ is $$$3$$$.
  • The mex of $$$[1, 2, 3]$$$ is $$$0$$$.
  • The mex of $$$[0, 2, 3]$$$ is $$$1$$$.
Given $$$n$$$ intervals of the form $$$[l_i, r_i]$$$, choose one integer from each interval such that the resulting sequence has the maximum possible MEX.
Input
  • The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$), the number of test cases.
  • For each test case:
    • The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$), the number of intervals.
    • The next $$$n$$$ lines each contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \leq l_i \leq r_i \leq n$$$), representing the $$$i$$$-th interval $$$[l_i, r_i]$$$.
It is guaranteed that the sum of the values of $$$n$$$ across all test cases does not exceed $$$10^6.$$$
Output

Print a single integer, the maximum possible mex of the sequence obtained by selecting one integer from each interval.

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

N. The Trap of Four Corners
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In one of the Squid Game challenges, players are tasked with positioning themselves within a circular arena. The challenge is to find the number of groups of four players that can stand on the same perfect circle within the arena, such that all four points lie on the circumference of the circle. The players are scattered randomly in the arena, and your task is to calculate how many such quadrilaterals can be formed.

You are given $$$n$$$ points in a 2D plane. Each point is represented by its coordinates ($$$x_{i},y_{i}$$$) for $$$1 \leq i \leq n$$$. You are tasked with finding the number of sets of four points that lie on the same circle.

Input

A single integer $$$n$$$ ($$$4 \leq n \leq 300$$$) representing the number of points in the plane.

The next $$$n$$$ lines contain two integers $$$x$$$ and $$$y$$$ representing the coordinates of each point($$$-1000 \leq x,y \leq 1000$$$).

Output

A single integer, the number of distinct quadrilaterals formed by four points that lie on the same circle.

Examples
Input
8
0 1
0 2
1 0
2 0
3 1
3 2
1 3
2 3
Output
70
Input
5
0 0
1 1
0 2
-1 1
0 1
Output
1
Input
5
0 0
1 1
-1 -1
1 -2
-2 1
Output
0
Note

In the first test, every point is included in the same circle, so the answer is choose $$$4$$$ out of $$$8$$$, which is $$$70$$$.

test $$$1$$$.

In the second test, only one quadruple of points is in the same circle, so the answer is $$$1$$$.

test $$$2$$$.

O. The Revolt of the Masked Guards
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the Squid Game, the Masked Guards are responsible for maintaining order and eliminating rebellious Players. However, the Guards have secretly grown resentful of the system and wish to overthrow the Front Man. The Guards have discovered a key insight: if a group of consecutive Guards in the circular formation is surrounded by strictly more Players, they will be overpowered and eliminated.

For example, if the initial formation is: $$$$$$11000100101$$$$$$ where 1 represents a Player and 0 represents a Masked Guard, the Players can initially attack the first three Guards, as they are surrounded by 4 Players: $$$$$$110001∗∗∗∗1$$$$$$ leaving the new formation as: $$$$$$11100101$$$$$$ The process continues until the Players take control of the entire arena.

The Guards, realizing the imminent threat, decide to swap their positions in a circular manner, attempting to find an arrangement where, after all possible attacks, the number of remaining Guards is greater than or equal to the initial number of Players.

Your task is to determine how many different valid rearrangements of the Guards and Players exist to ensure that the Guards can survive the rebellion. As these numbers can be very large, print the result modulo $$$998244353$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^6)$$$, representing the number of testcases.

For each testcase, you will be given two integers $$$k$$$ and $$$n$$$ $$$(1 \leq k \leq 10^6, 1 \leq n \leq 10^6)$$$, indicating the initial number of Players and the initial number of Guards.

Output

Print the answer modulo 998244353.

Example
Input
5
2 1
2 2
3 3
5 8
8 5
Output
0
16
216
204983294
0
Note

In the second test case if we enumerate the $$$4$$$ positions in the circular formation from $$$1$$$ to $$$4$$$ in clockwise order and we note the two players as $$$A$$$ and $$$B$$$ and the two guards as $$$C$$$ and $$$D$$$. Each permutation of this 4 letters represent a formation.

Then all possible valid rearrangements of the Guards and Players are : $$$ABCD$$$ , $$$BACD$$$ , $$$ABDC$$$ , $$$BADC$$$ , $$$CABD$$$ , $$$CBAD$$$ , $$$DABC$$$ , $$$DBAC$$$ , $$$CDAB$$$ , $$$CDBA$$$ , $$$DCAB$$$ , $$$DCBA$$$ , $$$ACDB$$$ , $$$ADCB$$$ , $$$BCDA$$$ , $$$BDCA$$$ so the answer is 16.

P. The Masked Guards' Line-Up
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In one of the Squid Game challenges, the Masked Guards randomly shuffle the players into a single line. However, only those players who remain in their original positions after the shuffle will survive. These survivors are the fixed points.

You are tasked with determining the expected number of survivors—the number of players who remain in their original positions after a random shuffle of the players.

You are given $$$t$$$ test cases. For each test case, you are given a single integer $$$n$$$, representing the number of players in the line-up. The Masked Guards shuffle the players into any possible permutations, each being equally likely. A fixed point (or survivor) is a position $$$i$$$ in the shuffled list where the player $$$i$$$ remains in the same position as their original number $$$i$$$.

Your task is to calculate the expected value of the number of survivors (fixed points) in a random shuffle of $$$n$$$ players for each test case.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^{5}$$$), the number of test cases.

Each of the next $$$t$$$ lines contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^{7}$$$), representing the number of players in the line-up.

It is guaranteed that the sum of all $$$n$$$ across the $$$t$$$ test cases does not exceed $$$10^{7}$$$.

Output

For each test case, output a single floating-point number, the expected number of survivors (fixed points), with an absolute or relative error of at most $$$10^{-6}$$$

Example
Input
2
1
2
Output
1.0000000
1.0000000