After the Battle of Yavin, the Rebel Alliance established the Echo Base as a temporary headquarters in Hoth. The harsh conditions on this frigid planet force the Rebel army to heavily rely on the Heating System for the hope of surviving and then continuing to fight against the Galactic Empire. The Heating System is not only important in keeping the soldiers warm, but also for maintaining various droids and weapons.

The Heating System requires at least ~x~ units of energy to be effective. The Rebels prepared ~n~ fusion generators, where the ~i~-th generator can release ~a_i~ units of energy. If the Rebels use multiple generators, the amount of released power can be calculated as the sum of released power from each of the used generators.

A generator is called faultable if, when that generator is faulty, the remaining ~n-1~ generators would still release at least ~x~ units of power for the Heating System.

Speculated that harsh weather in Hoth might defect one generator, Luke asked R2-D2 to count the number of faultable generators. R2-D2 calculated and returned the value ~k~.

Unfortunately, after taking the ~k~ from R2-D2, Luke forgot the value ~x~. He wants to check if there exists a non-negative integer ~x~ such that there are exactly ~k~ faultable generators among ~n~ prepared ones.

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 100~). The description of the test cases is as follows.

The first line of each test case contains two integers ~n, k~ (~2 \leq n \leq 100, 0 \leq k \leq n~), the number of generators and the number of faultable generators calculated by R2-D2, respectively.

The second line of each test case contains ~n~ integers ~a_1, a_2, \dots, a_n~ (~1 \leq a_i \leq 1000~), the amount of released power by the generators.

Output

For each test case, if there exists a non-negative integer ~x~ such that there are exactly ~k~ faultable generators, print YES; otherwise, print NO.

Sample Input 1

6
5 0
1 3 5 3 1
5 1
1 3 5 3 1
5 2
1 3 5 3 1
5 3
1 3 5 3 1
5 4
1 3 5 3 1
5 5
1 3 5 3 1

Sample Output 1

YES
NO
YES
NO
YES
YES

The Jedi Trials can be considered an exam in the Jedi Temple, which tests Padawans many important skills before promoting them to be Jedi Knights, which include Force abilities, mental discipline, etc. Lightsabers are versatile and powerful weapons, so it is required for a Padawan to master them. Therefore, a lightsaber duel is one of the most appealing phases during the Jedi Trials. The upcoming Jedi Trials will be the competition of ~k~ Padawans.

In preparation for the upcoming Jedi Trials, Master Yoda has made ~n~ (~n \geq k~) lightsabers; the ~i~-th lightsaber has the length ~l_i~. In order to ensure fairness between all Padawans during the lightsaber duel, the two lightsabers of two Padawans in the duel must have the same length. Because there are ~k~ Padawans, Yoda needs to have at least ~k~ lightsabers that have equal lengths.

Because it consumes a lot of time to make new lightsabers, Yoda chooses to adjust the length of existing ones. Yoda prefers the short lightsabers over long lightsabers because they highlight more skills from Padawans, such as reflexes and versatility. Thus, he will only shorten lightsabers but not lengthen them. Yoda wants to know at least how many lightsabers he has to shorten before obtaining ~k~ lightsabers that have the same length. Can you help him?

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10^4~). The description of the test cases is as follows.

The first line of each test case contains two integers ~n, k~ (~1 \leq k \leq n \leq 10^6~), the number of lightsabers that Yoda made and the number of Padawans, respectively.

The next line of each test case contains ~n~ integers ~l_1, l_2, \dots, l_n~ (~1 \leq l_i \leq 10^9~), lengths of the lightsabers.

The sum of ~n~ over all test cases does not exceed ~10^6~.

Output

For each test case, print the minimum number of lightsabers to be shortened before getting ~k~ lightsabers having equal length.

Sample Input 1

3
4 2
1 2 3 4
6 6
1 1 1 1 1 1
5 4
4 4 4 3 2

Sample Output 1

1
0
3

After completing the Death Star, the Galactic Empire secretly began constructing Death Star II with the aim of consolidating power and creating a more powerful deterrent. After the Death Star was destroyed due to a serious design flaw, Palpatine not only had to expedite the construction of Death Star II, but he also set higher demands for the engineers building it. Not only must they be skilled builders, but they also need to be proficient in mathematics and programming. Each engineer applying will be asked the following problem:

• Given an integer ~n~ (~1 \leq n < 2^{30}~), find two positive integers ~x, y~ (~1 \leq x, y < 2^{60}~) such that ~x \oplus y = gcd(x, y) = n~.

Although you are a novice engineer, you have an advantage over other candidates with your programming experience. Will you be able to pass this test?

Input

Each test contains multiple test cases.The first line contains the number of test cases ~t~ (~1 \leq t \leq 10^4~).

The only line of each test case contains an integer ~n~ (~1 \leq n < 2^{30}~).

Output

For each test case, print a single line containing two integers ~x, y~ (~1 \leq x, y < 2^{60}~) that satisfy the condition ~x \oplus y = gcd(x, y) = n~.

Sample Input 1

2
2
5

Sample Output 1

12 14
10 15

Anakin and Padmé are enjoying a happy life on Naboo. Today, they are playing a game with a string to maintain their affection. The game will start with a string ~s~ and an empty string ~t~. Anakin and Padmé will take turns, with Padmé going first. In each step, the player will:

• Choose a character ~c~ from ~s~ and remove ~c~ from ~s~.

• Choose to append or prepend ~c~ to ~t~.

The game will end when the string ~s~ is empty. If the final string ~t~ is a palindrome, Padmé wins; otherwise, Anakin wins. Find which player will win if both players play optimally.

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10^4~).

The only line of each test case contains a string ~s~ (~1 \leq |s| \leq 10^6~) that consists of lowercase Latin characters.

The sum of ~|s|~ over all test cases does not exceed ~10^6~.

Output

For each test case, print a single line with the last name of the winner, assuming both players play optimally. If Padmé wins, print Amidala; otherwise, print Skywalker.

Sample Input 1

4
aaaa
abcd
aabbc
abbbc

Sample Output 1

Amidala
Skywalker
Amidala
Skywalker

In the galaxy, there are ~n~ planets. Each planet may or may not have residents. Due to the vast distances in the galaxy, residents must travel from a planet to other planets through hyperspace. There are ~n-1~ bidirectional lanes in hyperspace, and the residents of the galaxy can use route ~i~ to hyperjump from planet ~u_i~ to planet ~v_i~ or vice versa. These routes ensure that from any given planet, residents can always travel to any other planet through one or more hyperjumps. Each hyperjump will cost one hyperfuel.

Believed to be dead, Sidious has unexpectedly returned and is more powerful than ever. He is hiding on one of the ~n~ planets in the galaxy. Although Rey is very worried about this return, she feels somewhat reassured knowing that she always has the support of the residents of the galaxy: for each planet that has residents, they will gather the bravest residents to one ship and travel to the planet where Sidious is by the routes in hyperspace that minimize the number of hyperjumps.

C-3PO has calculated that if Sidious is hiding on planet ~i~, traveling from other planets to planet ~i~ would cost ~a_i~ hyperfuels in total. From this information, Rey wants to determine which planets have residents or to identify if there is an error in C-3PO's calculations. As a true coder, can you help Rey?

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10^{4}~). The description for the test cases is as follows.

The first line of each test case contains an integer ~n~ (~1 \leq n \leq 10^6~), the number of planets in the galaxy.

The next line of each test case contains ~n~ integers ~a_1, a_2, \dots a_n~ (~0 \leq a_i \leq 10^{12}~), the amount of hyperfuels consumed if Sidious is hiding on planet ~i~, calculated by C-3PO.

For the next ~n-1~ lines, each line contains two integers ~u_i, v_i~ (~1 \leq u_i, v_i \leq n~), denoting endpoints of the ~i~-th lane in hyperspace.

It is possible to travel from any given planet to any other planet through hyperspace.

The sum of ~n~ over all test cases does not exceed ~10^6~.

Output

For each test case, if there does not exist a set of planets that is compliant with C-3PO's calculation, print a single line that contains NO.

Otherwise, print as follows.

The first line contains YES.

The next line contains ~n~ binary digits ~b_1, b_2, \dots, b_n~ (If the ~i~-th planet has residents, ~b_i=1~; otherwise, ~b_i=0~).

If there are multiple sets of planets that are compliant with C-3PO's calculation, you can output any of them.

Sample Input 1

4
4
2 5 3 3
1 2
1 3
1 4
2
1 1
1 2
2
0 0
1 2
3
1 2 1
1 2
2 3

Sample Output 1

YES
1 0 1 1 
YES
1 1 
YES
0 0 
NO

Notes

We consider the first test case.

If Sidious is hiding on planet ~1~:

• Residents from planet ~1~ do not need to make any hyperjump.

• Residents from planet ~3~ need to make ~1~ hyperjump (through lane ~2~).

• Residents from planet ~4~ need to make ~1~ hyperjump (through lane ~3~).

In total, there are ~1+1=2~ hyperjumps, which cost ~2~ hyperfuels.

If Sidious is hiding on planet ~2~:

• Residents from planet ~1~ need to make ~1~ hyperjump (through lane ~1~).

• Residents from planet ~3~ need to make ~2~ hyperjumps (through lane ~2~ then lane ~1~).

• Residents from planet ~4~ need to make ~2~ hyperjumps (through lane ~3~ then lane ~1~).

In total, there are ~1+2+2=5~ hyperjumps, which cost ~5~ hyperfuels.

If Sidious is hiding on planet ~3~:

• Residents from planet ~1~ need to make ~1~ hyperjump (through lane ~2~).

• Residents from planet ~3~ do not need to make any hyperjump.

• Residents from planet ~4~ need to make ~2~ hyperjumps (through lane ~3~ then lane ~2~).

In total, there are ~1+2=3~ hyperjumps, which cost ~3~ hyperfuels.

If Sidious is hiding on planet ~3~:

• Residents from planet ~1~ need to make ~1~ hyperjump (through lane ~3~).

• Residents from planet ~3~ need to make ~2~ hyperjumps (through lane ~2~ then lane ~3~).

• Residents from planet ~4~ do not need to make any hyperjumps.

In total, there are ~1+2=3~ hyperjumps, which cost ~3~ hyperfuels.

After receiving the mission to produce the clone trooper for the Galactic Republic, the Kaminoans realized that issues in their cloning technology had resulted in clones of varying heights, even though they were all created from the same genetic template. They recognized that, in preparation for the Clone Wars, these soldiers needed to be arranged in order of height from shortest to tallest.

Initially, there are ~n~ clones lined up and numbered from ~1~ to ~n~, with the first clone having height ~h_1~, the second clone having height ~h_2~, ~\dots~, and the last clone having height ~h_n~. To rearrange the line, the Kaminoans perform the following operation an arbitrary number of times:

• Choose an index ~i~ (~1 \leq i \leq n~), and let ~j~ be the largest index such that ~j < i~ and ~h_j > h_i~. (Note that if ~j~ does not exist, this operation is not considered valid.)

• Swap the positions of clone ~i~ and clone ~j~ (and simultaneously swap ~h_i~ and ~h_j~).

Count the number of ways of rearranging clones such that, in the end, the heights of the ~n~ clones are arranged from shortest to tallest. Two ways of rearrangement are considered different if the number of operations is different or if there exists a position where the pair ~(i, j)~ is different. Since the result can be very large, you only need to output the remainder when it is divided by ~998244353~.

Input

The first line contains an integer ~n~ (~1 \leq n \leq 10^6~), the number of clones.

The next line contains ~n~ distinct positive integers ~h_1, h_2, \dots h_n~ (~1 \leq h_i \leq 10^9~), the heights of the clones.

Output

Print the single line with the number of ways of rearrangement modulo ~998244353~.

Sample Input 1

3
17 70 13

Sample Output 1

1

Sample Input 2

7
174 177 172 176 175 171 173

Sample Output 2

7567560

With the plan to capture Luke and lure him to the Dark Side of the Force, Vader has brought ~n~ followers to Cloud City. Among them are bounty hunters, storm troopers, and imperial officers. The ~i~-th follower has a capability of ~a_i~. To carry out this complex mission, Vader will divide the ~n~ followers into one or more groups. He will calculate the effectiveness of a division as follows:

• Let ~k~ be the number of groups, and calculate the capability ~s_i~ of group ~i~ by summing the capabilities of all members in that group.

• The effectiveness of the division is calculated as ~\gcd(s_1, s_2, \dots, s_k).~

Vader wants to calculate the total effectiveness across all divisions. Two divisions are considered different if there exist two followers in the same group in one division but in different groups in the other division.

Input

The first line contains a positive integer ~n~ (~1 \leq n \leq 16~), the number of followers Vader has brought.

The second line contains ~n~ positive integers ~a_1, a_2, \dots, a_n~ (~1 \leq a_i \leq 100~), describing the capabilities of the followers that Vader has brought.

Output

Print a single line with the sum of effectiveness across all divisions.

Sample Input 1

4
1 2 3 4

Sample Output 1

32

Sample Input 2

6
1 2 4 8 16 32

Sample Output 2

357

Kashyyyk is the home planet of the Wookiees, famous for its dense forests, giant Wroshyr trees, and rich ecosystem. This planet also holds strategic importance for the Republic, which is why it has been targeted in the attack by the Separatists.

To plan the attack, the Separatists have described the surface of the planet as a ~2D~ plane, and they have identified ~n~ Wroshyr trees, with the ~i~-th tree located at integer coordinates ~p_i = (x_i, y_i)~. While the command was pondering the next step, a tactical droid realized that if the Separatists could capture the trees with indices ~i_1, i_2, \dots, i_k~, they could easily encircle the area formed by the convex hull of the points ~p_{i_1}, p_{i_2}, \dots, p_{i_k}~. Therefore, he proposed a way to calculate the importance of each Wroshyr tree as follows:

• Randomly select a permutation ~q_1, q_2, \dots, q_n~ with values from ~1~ to ~n~.

• Let ~s_i~ be the area of the convex hull formed by ~i~ points ~p_{q_1}, p_{q_2}, \dots, p_{q_i}~.

• For each ~i~, the importance of tree ~q_i~ is calculated using the formula ~s_i - s_{i-1}~.

For each ~i~, let ~e_i~ be the expected value of the importance of tree ~i~. You need to find and print the value ~2 \cdot n! \cdot e_i~ (it can be proven that these values are always integers). Since these answers can be huge, you only need to print the remainder when divided by ~998244353~.

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10~). The description of the test cases is as follows.

The first line of the test cases contains an integer ~n~ (~1 \leq n \leq 2000~), the number of Wroshyr trees on the planet.

For the next ~n~ lines, the ~i~-th line contains two integers ~x_i, y_i~ (~0 \leq x_i, y_i \leq 10^9~), the coordinates of the ~i~-th Wroshyr tree in the ~2D~ plane.

There are no two trees at the same locations, and there are not three trees collinear.

The sum of ~n~ over all test cases does not exceed ~2000~.

Output

For each test case, print ~n~ integers, with the ~i~-th integer being ~2 \cdot n! \cdot e_i~ modulo ~998244353~.

Sample Input 1

3
3
0 0
0 4
4 4
4
0 0
0 4
4 4
4 0
4
0 0
0 4
10 10
7 0

Sample Output 1

32 32 32
192 192 192 192
444 540 876 780

Tatooine is a desert planet located at the edge of the Galaxy, and it is not under the jurisdiction of the Galactic Republic. Therefore, there are a few special points in the payment methods there. Merchants not only do not accept the credit methods of the Republic but also do not accept ..... change.

Obi-Wan learned about this the first time he came here, so he prepared ~n~ coins with denominations ~a_1, a_2, \dots, a_n~. He will choose ~l, r~ (~1 \leq l \leq r \leq n~) and bring the coins ~a_l, a_{l + 1}, \dots, a_r~ for his return to Tatooine. Obi-Wan defines ~f(l, r)~ as the smallest amount of money that he cannot pay with the coins ~a_l, a_{l + 1}, \dots, a_r~.

For example, if ~a = [1, 3, 2]~, then ~f(1, 3) = 7~ (because Obi-Wan can pay every amount from ~1~ to ~6~ but does not have enough money to pay ~7~), and ~f(1, 2) = 2~ (although Obi-Wan has enough money to pay the amount ~2~, he still cannot pay because change is not accepted on Tatooine).

Feeling that calculating a single value is too simple, Obi-Wan wants to calculate the sum of ~f~ for all pairs of positive integers ~(l, r)~ such that ~1 \leq l \leq r \leq n~, formally ~\sum_{l=1}^{n}\sum_{r=l}^{n} f(l, r)~.

Can you help him?

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10^4~). The description of the test cases is as follows.

The first line of each test case contains an integer ~n~ (~1 \leq n \leq 10^6~), the number of coins that Obi-Wan prepared.

The second line contains ~n~ positive integers ~a_1, a_2, \dots, a_n~ (~1 \leq a_i \leq 10^{12}~), the denominations of Obi-Wan's coins.

The sum of ~n~ over all test cases does not exceed ~10^6~.

Output

For each test case, print a single line with the ~\sum_{l=1}^{n}\sum_{r=l}^{n}f(l, r)~. Since the answer can be very large, you only need to output it in modulo ~998244353~.

Sample Input 1

3
6
1 3 5 7 9 1
6
1 2 4 8 16 32
10
9 7 5 3 1 1 3 5 7 9

Sample Output 1

57
141
615