TheForces Round #13 (Boombastic-Forces)
A. Human Readable
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Akbar has a file of size of $$$m$$$ bytes on his hard drive. He wants to display the approximate size of this file in a "human readable" way.

Any "human-readable" representation is in the form of "$$$n$$$U" which includes two parts :

  • "number" that is displayed with $$$n$$$ which is in the range $$$[1, 1023]$$$.
  • "unit" represented by U is a string of lowercase and uppercase English letters and equals "B", "KiB" or "MiB".

For example, a "37MiB" representation is a "human-readable" representation. which the "number" part is $$$37$$$ and the "unit" part is "MiB". But "$$$12$$$ bytes" (because byte is not allowed among the words) or "40000KiB" (the number is more than $$$1023$$$) is not "readable by humans".

Also we know that "B" means byte and :

  • Each "1KiB" is equal to "1024B"
  • Each "1MiB" is equal to "1024KiB"

Note that we cannot always display the exact size of a file in a "human-readable" way, and sometimes we have to approximate it. We ask you to always round down when approximating. To better understand this issue, pay attention to the samples.

Input

In the first line of input ybe given $$$t$$$ which shows the number of testcases :

$$$1 \le t \le 100$$$.

In the next $$$t$$$ lines you'll be given a number $$$m$$$ which shows the size of Akbar's file.

$$$1 \le m \le 10^9$$$.

Output

In each line, print the size of the file related to that test in a "human-readable" way.

Note that the judging system is case sensitive.

According to the limitations of the question, it can be proved that the answer to the problem is always unique.

Example
Input
3
29
1401
14510629
Output
29B
1KiB
13MiB
Note

The first test's file size is $$$29$$$ bytes. So it's human-readable representation is "29B".

The second test's file size is $$$1401$$$ bytes. Considering that the "number" in the "human-readable" display must be in the range of $$$1$$$ to $$$1023$$$, the display of "1401B" or "0MiB" is not correct and the correct display is "1KiB".

The third test's file size is $$$14510629$$$. Due to the limitation of "number" in "human readable" display, we must use the "MiB" unit. The closest number is $$$13.8$$$, but the size must be an integer and positive, and since we have to approximate downwards, we choose "13MiB".

B. Least SigDig
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given two numbers $$$n$$$ and $$$m$$$, Your task is to calculate $$$n × 245^m$$$ and then print the least significant digit of it.

Input

The first line contains single integer $$$t$$$ the number of tests.

$$$1 \le t \le 10^3$$$.

Output

Each test contains two numbers, $$$n$$$ and $$$m$$$ respectively.

$$$0 \le n, m \le 10^9$$$.

Example
Input
3
1 1
2 1
2 2
Output
5
0
0
Note

For each test, print one integer in one line — the answer to the problem.

C. Super Binary Numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Amir, believes in binary numbers. After solving lots of binary-boy problems, He managed to come up with a problem about binary numbers.

The problem is as follows :

Amir calls a number super binary number if it has at least two of the following properties :

  • the number is palindrome in hexadecimal presentation.
  • the number is palindrome in binary presentation.
  • the number is palindrome in decimal presentation.

Your job is to help Amir to determine if a number is a super binary number or not.

Input

The first line of input shows the number of test cases $$$t$$$ :

$$$1 \le t \le 10^3$$$.

Each of following $$$t$$$ lines contains an integer $$$n$$$ :

$$$1 \le n \le 10^3$$$.

Output

For each test case, if the number is a super binary number print "ghavi", otherwise print "fanni khordim".

Example
Input
3
85
69
17
Output
ghavi
fanni khordim
ghavi
Note

Testcase $$$1$$$ :

$$$85 = (1010101)_2 \rightarrow Palindrome$$$.

$$$85 = (55)_{16} \rightarrow Palindrome$$$.

D. Yet another permutation problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Amir and Akbar have got two arrays, each consisting a permutation of $$$1$$$ to $$$n$$$, They want to play a game, the goal of the game is making the arrays similar, two arrays are similar if they have same length and all of the elements in each index of both arrays are equal.

In each turn one can remove a single integer from his array, If both play optimally, find out the minimum number of turns it takes to finish the game.

Input

The first line of input shows the number of test cases $$$t$$$, Each test case will contain $$$3$$$ lines. The first line contains a single integer $$$n$$$, The length of each array.

$$$1 \le n \le 10^5$$$.

Second and third line each will contain $$$n$$$ space separated integers indicating the numbers in permutations $$$A$$$ and $$$B$$$ respectively.

It's guaranteed that sum of $$$n$$$ overall testcases will not exceed $$$10^5$$$.

Output

For each test case, print a single integer in a line, the minimum number of turns to finish the game.

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

E. Shift in TheForces
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given a string $$$s$$$ of length $$$n$$$ with lowercase English letters, Shift of $$$s$$$ means to remove the first $$$k$$$ letters and transfer them the the end of the string which $$$(1 \le k \le n)$$$.

In the other words :

At first $$$s = $$$ $$$s_{1}s_{2},...s_{k},...s_{n}$$$ after the operation $$$s = $$$ $$$s_{k+1},s_{k+2},...,s_{n},s_{1},s_{2},...s_{k}$$$.

Now you're given $$$s$$$ and $$$n$$$, Your task is to find the lexicographically minimum string among all $$$n$$$ shifts of $$$s$$$.

Input

In the first line of input you'll be given an integer $$$n$$$ which $$$n$$$ is length of the string ($$$1 \le n \le 3 * 10^5$$$).

The second line of testcase consists the string $$$s$$$.

Output

Print the lexicographically minimum string among all shifts of $$$n$$$.

Example
Input
4
nima
Output
anim
Note

All the shifts of "nima" are : "iman", "mani", "anim", "nima", which "anim" is the lexicographically minimum among all of them.

F. Make Zero
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary string $$$s$$$ that consists of only $$$0$$$ and $$$1$$$. You can choose some substring of the format $$$10..0..01$$$ i.e. choose two non-adjacent indexes $$$i$$$ and $$$j$$$ and $$$(i + 1 \lt j)$$$, such that $$$s_i = 1$$$ and $$$s_j = 1$$$ and $$$s_k = 0$$$ for all $$$i \lt k \lt j$$$, then replace substring $$$s[i \dots j]$$$ with single $$$0$$$.

Your task is to find out if you can make $$$s$$$ is equal to $$$0$$$ after performing the operation any number of times.

Input

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

The each test case contains a string $$$s$$$ $$$(1 \le |s| \le 10^4)$$$ — consists of $$$0$$$ and $$$1$$$.

Output

For each test case, if possible YES, else NO.

Example
Input
6
0
10101
101101
10001101011
1110000111
1100011100111
Output
YES
NO
NO
YES
YES
YES

G. Permutation Removal
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Amir has a permutation of $$$1$$$ to $$$n$$$, where $$$n$$$ is an even number. In each step, Amir selects two adjacent elements of the array, whose the number on the left side is greater than the number on the right side, then removes both and pastes the remaining numbers of the array together.

Now Amir wants to find the number of ways to remove all permutation's elements. Since the number of ways may be too large, Amir asks you to find the answer for him and print the answer modulo $$$10^9 + 7$$$.

Input

In the first line of input, $$$n$$$ is given which $$$n$$$ is even.

$$$2 \le n \le 500$$$.

In the second line of input you'll be given a permutation of $$$1$$$ to $$$n$$$.

Output

Print the answer modulo $$$10^9 + 7$$$.

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

In the first sample we have $$$3$$$ ways of removing the arrays' elements :

$$$[6, 4, 3, 2, 1, 5] \rightarrow [6, 2, 1, 5] \rightarrow [6, 5] \rightarrow []$$$

$$$[6, 4, 3, 2, 1, 5] \rightarrow [6, 4, 1, 5] \rightarrow [6, 5] \rightarrow []$$$

$$$[6, 4, 3, 2, 1, 5] \rightarrow [6, 4, 3, 5] \rightarrow [6, 5] \rightarrow []$$$