TheForces Round #10 (TEN-Forces)
A. Reading Books
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

O–O loves to read books everyday.

He has $$$n$$$ days and $$$m$$$ books. In the $$$i$$$-th day, O–O reads $$$a_i$$$ pages. The array $$$b$$$ represents the number of pages in books.

In the $$$i$$$-th day, he wants to know the maximum number of books he already finished.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n , m \le 2 ⋅ 10^5)$$$ — the length of the array $$$a$$$ and $$$b$$$.

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

The third line of each test case contains $$$m$$$ integers $$$b_1,b_2 \dots b_m$$$ $$$(1 \le b_i \le 10^9)$$$.

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

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

Output

For each test case, output $$$n$$$ integers.

Example
Input
2
4 3
7 5 2 1
6 8 9
5 6
7 12 23 15 29
10 9 6 8 13 1
Output
1 1 2 2 
2 3 5 6 6

B. Two Squares
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

You are given an non-negative integer $$$n$$$.

Your task is to find the the count of $$$x$$$ $$$(0 \le x \le n)$$$ that can be showed that $$$x = a^2 + b^2$$$ ($$$a$$$ and $$$b$$$ are integers).

Input

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

The each test case contains a single integer $$$n$$$ $$$(0 \le n \le 10^7)$$$.

Output

For each test case, output a single integer.

Example
Input
4
1
6
576
10000000
Output
2
5
200
1985460
Note

In the second test case, it can be proven that $$$3$$$ and $$$6$$$ can not be showed that $$$a^2 + b^2$$$.

C. Lucky Numbers
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

We know that O–O read books everyday. He learned about lucky numbers.

If their decimal representation doesn't contain digits other than $$$4$$$ and $$$7$$$. For example, numbers $$$47, 744, 4$$$ are lucky and $$$5, 17, 467$$$ are not.

Now, he has the large number $$$n$$$, his task is to find the number of lucky numbers not greater than $$$n$$$.

Print it modulo 998244353.

The number doesn't have leading zeroes.

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.

The each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^{100})$$$.

Output

For each test case, output a single integer.

Example
Input
3
47
748
774411
Output
4
12
110

D. Good Sets
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

$$$S$$$ is the set of certain integers. If the difference between any two integers in the set is not greater than $$$k$$$, $$$S$$$ is considered good.

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

Your task is to find the number of non-empty good subarrays and non-empty good subsequences.

Print them modulo 998244353.

Input

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

The first line of each test case contains two integers $$$n$$$ $$$(1 \le n \le 2 ⋅ 10^5)$$$ and $$$k$$$ $$$(0 \le k \le 10^{18})$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2 \dots a_n$$$ $$$(-10^{18} \le a_i \le 10^{18})$$$.

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

Output

For each test case, output two integers — good subarrays and good subsequences.

Example
Input
2
4 2
4 5 8 3
7 21
32 19 -2 -5 0 -11 9
Output
5 8
19 41

E. Again Last Digit
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

$$$n!$$$ is factorial of $$$n$$$.

$$$f_n$$$ is $$$n$$$-th fibonacci number.

$$$f_0$$$ $$$=$$$ $$$0$$$

$$$f_1$$$ $$$=$$$ $$$1$$$

$$$f_n$$$ $$$=$$$ $$$f_{n - 1}$$$ + $$$f_{n - 2}$$$

You are given an integer $$$n$$$.

$$$S = f_0^{0!} + f_1^{1!} + f_2^{2!} + f_3^{3!} + \dots + f_n^{n!}$$$

In other words, sum of $$$f_i$$$ power of $$$i!$$$

Your task is to find the last digit of $$$S$$$.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$0 \le n \le 10^{18}$$$).

Output

For each test case, output a single integer.

Example
Input
3
4
87
4619
Output
7
8
4

F. OR Pairs
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$.

Your task is to find the number of pairs $$$a$$$ and $$$b$$$ that:

  • $$$0 \le a \le b$$$;
  • $$$a$$$ | $$$b \le n$$$.

| means Bitwise OR Operation.

Input

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

The each test case contains a single integer $$$n$$$ $$$(0 \le n \le 10^{9})$$$.

Output

For each test case, output a single integer — the number of pairs.

Example
Input
5
0
1
6
7
8
Output
1
3
22
36
38