vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Samba has annoyed gabbar once again. But this time gabbar has all the six bullets in his pistol. the only way for samba to escape is to give an answer to gabbar's mathematical problem. The problem is to find the number with maximum occurence in prime factorization of factorial of number n.
If more than one answer is possible then samba would have to print the largest number.hail samba !

Input

first line contains T . no of test cases 

next T lines contains n .

Output

number with maximum occurrence in prime factorization of factorial of the number 

Constraint

0 < T < 100

2 ≤ n ≤ 20

SAMPLE INPUT
1
4

SAMPLE OUTPUT
2

Explanation

factorial of 4 = 24 

prime factorization of 24 is 2^3*3^1

thus ans is 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Osama is a maths enthusiast. Numbers and equations never fails to amaze him. Recently he started exploring a weird problem. The explanation of the problem he is working on, is given below.
He takes the equation,
ax1+bx2+cx3+.... = 1, for some integers x1,x2,x3,...
He likes to analyze the properties of this equation. Given a set of values a,b,c,... can we find whether the given set of integers complies with the above equation for some set of integers x1,x2,x3... ?
Osama being a genius, devised a method to solve this problem. Now he challenges you. Given a set of positive integers (a,b,c,...) you have to say whether it can solve the above equation for some integers (x1,x2,x3,...).

First line of the input contains T, the total number of testcases to be processed. Then T sets of data follow.
Each set of data consists two lines. First line contains N, followed by N space separated positive integers in the next line, the set of integers to be processed.

1 ≤ T ≤ 10

1 ≤ N ≤ 100

1 ≤ positive integers in given set ≤ 10000000

Output a string for each testcase in a new line. Print YES if it can solve the above given equation for some set of integers (x1,x2,x3,...) . Or else Print NO.

SAMPLE INPUT
2
4
6 27 4 5
4
2 4 6 8

SAMPLE OUTPUT
YES
NO

Explanation

Sample input has two testcases. 
First testcase has 4 numbers in the set. (6,27,4,5).
60 + 27(-2) + 40 + 511 = -54+55 = 1 ,thus print YES.
In second testcase, we cant form any combination of integers to solve the equation, thus print NO.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Do you know Professor Saeed? He is the algorithms professor at Damascus University. Yesterday, he gave his students hard homework (he is known for being so evil) - for a given binary string $S$, they should compute the sum of $F(S, L, R)$ over all pairs of integers $(L, R)$ ($1 \le L \le R \le |S|$), where the function $F(S, L, R)$ is defined as follows:
- Create a string $U$: first, set $U = S$, and for each $i$ ($L \le i \le R$), flip the $i$-th character of $U$ (change '1' to '0' or '0' to '1').
- Then, $F(S, L, R)$ is the number of valid pairs $(i, i + 1)$ such that $U_i = U_{i+1}$.
As usual, Professor Saeed will give more points to efficient solutions. Please help the students solve this homework.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single string $S$.

-----Output-----
For each test case, print a single line containing one integer $\sum_{1 \le L \le R \le |S|} F(S, L, R)$.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le |S| \le 3 \cdot 10^6$
- the sum of $|S|$ over all test cases does not exceed $6 \cdot 10^6$

-----Subtasks-----
Subtask #1 (50 points):
- $1 \le |S| \le 300$
- the sum of $|S|$ over all test cases does not exceed $600$
Subtask #2 (50 points): original constraints

-----Example Input-----
1
001

-----Example Output-----
6

-----Explanation-----
Example case 1:
- $L = 1, R = 1$: $U$ is "101", $F = 0$
- $L = 2, R = 2$: $U$ is "011", $F = 1$
- $L = 3, R = 3$: $U$ is "000", $F = 2$
- $L = 1, R = 2$: $U$ is "111", $F = 2$
- $L = 2, R = 3$: $U$ is "010", $F = 0$
- $L = 1, R = 3$: $U$ is "110", $F = 1$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Omkar is building a house. He wants to decide how to make the floor plan for the last floor.

Omkar's floor starts out as $n$ rows of $m$ zeros ($1 \le n,m \le 100$). Every row is divided into intervals such that every $0$ in the row is in exactly $1$ interval. For every interval for every row, Omkar can change exactly one of the $0$s contained in that interval to a $1$. Omkar defines the quality of a floor as the sum of the squares of the sums of the values in each column, i. e. if the sum of the values in the $i$-th column is $q_i$, then the quality of the floor is $\sum_{i = 1}^m q_i^2$.

Help Omkar find the maximum quality that the floor can have.


-----Input-----

The first line contains two integers, $n$ and $m$ ($1 \le n,m \le 100$), which are the number of rows and number of columns, respectively.

You will then receive a description of the intervals in each row. For every row $i$ from $1$ to $n$: The first row contains a single integer $k_i$ ($1 \le k_i \le m$), which is the number of intervals on row $i$. The $j$-th of the next $k_i$ lines contains two integers $l_{i,j}$ and $r_{i,j}$, which are the left and right bound (both inclusive), respectively, of the $j$-th interval of the $i$-th row. It is guaranteed that all intervals other than the first interval will be directly after the interval before it. Formally, $l_{i,1} = 1$, $l_{i,j} \leq r_{i,j}$ for all $1 \le j \le k_i$, $r_{i,j-1} + 1 = l_{i,j}$ for all $2 \le j \le k_i$, and $r_{i,k_i} = m$.


-----Output-----

Output one integer, which is the maximum possible quality of an eligible floor plan.


-----Example-----
Input
4 5
2
1 2
3 5
2
1 3
4 5
3
1 1
2 4
5 5
3
1 1
2 2
3 5

Output
36



-----Note-----

The given test case corresponds to the following diagram. Cells in the same row and have the same number are a part of the same interval.

 [Image] 

The most optimal assignment is:

 [Image] 

The sum of the $1$st column is $4$, the sum of the $2$nd column is $2$, the sum of the $3$rd and $4$th columns are $0$, and the sum of the $5$th column is $4$.

The quality of this floor plan is $4^2 + 2^2 + 0^2 + 0^2 + 4^2 = 36$. You can show that there is no floor plan with a higher quality.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n points marked on the plane. The points are situated in such a way that they form a regular polygon (marked points are its vertices, and they are numbered in counter-clockwise order). You can draw n - 1 segments, each connecting any two marked points, in such a way that all points have to be connected with each other (directly or indirectly).

But there are some restrictions. Firstly, some pairs of points cannot be connected directly and have to be connected undirectly. Secondly, the segments you draw must not intersect in any point apart from the marked points (that is, if any two segments intersect and their intersection is not a marked point, then the picture you have drawn is invalid).

How many ways are there to connect all vertices with n - 1 segments? Two ways are considered different iff there exist some pair of points such that a segment is drawn between them in the first way of connection, but it is not drawn between these points in the second one. Since the answer might be large, output it modulo 10^9 + 7.


-----Input-----

The first line contains one number n (3 ≤ n ≤ 500) — the number of marked points.

Then n lines follow, each containing n elements. a_{i}, j (j-th element of line i) is equal to 1 iff you can connect points i and j directly (otherwise a_{i}, j = 0). It is guaranteed that for any pair of points a_{i}, j = a_{j}, i, and for any point a_{i}, i = 0.


-----Output-----

Print the number of ways to connect points modulo 10^9 + 7.


-----Examples-----
Input
3
0 0 1
0 0 1
1 1 0

Output
1

Input
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

Output
12

Input
3
0 0 0
0 0 1
0 1 0

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke is making sugar water in a beaker.
Initially, the beaker is empty. Snuke can perform the following four types of operations any number of times. He may choose not to perform some types of operations.
 - Operation 1: Pour 100A grams of water into the beaker.
 - Operation 2: Pour 100B grams of water into the beaker.
 - Operation 3: Put C grams of sugar into the beaker.
 - Operation 4: Put D grams of sugar into the beaker.
In our experimental environment, E grams of sugar can dissolve into 100 grams of water.
Snuke will make sugar water with the highest possible density.
The beaker can contain at most F grams of substances (water and sugar combined), and there must not be any undissolved sugar in the beaker.
Find the mass of the sugar water Snuke will make, and the mass of sugar dissolved in it.
If there is more than one candidate, any of them will be accepted.
We remind you that the sugar water that contains a grams of water and b grams of sugar is \frac{100b}{a + b} percent.
Also, in this problem, pure water that does not contain any sugar is regarded as 0 percent density sugar water.

-----Constraints-----
 - 1 \leq A < B \leq 30
 - 1 \leq C < D \leq 30
 - 1 \leq E \leq 100
 - 100A \leq F \leq 3 000
 - A, B, C, D, E and F are all integers.

-----Inputs-----
Input is given from Standard Input in the following format:
A B C D E F

-----Outputs-----
Print two integers separated by a space.
The first integer should be the mass of the desired sugar water, and the second should be the mass of the sugar dissolved in it.

-----Sample Input-----
1 2 10 20 15 200

-----Sample Output-----
110 10

In this environment, 15 grams of sugar can dissolve into 100 grams of water, and the beaker can contain at most 200 grams of substances.
We can make 110 grams of sugar water by performing Operation 1 once and Operation 3 once.
It is not possible to make sugar water with higher density.
For example, the following sequences of operations are infeasible:
 - If we perform Operation 1 once and Operation 4 once, there will be undissolved sugar in the beaker.
 - If we perform Operation 2 once and Operation 3 three times, the mass of substances in the beaker will exceed 200 grams.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nikolay got a string $s$ of even length $n$, which consists only of lowercase Latin letters 'a' and 'b'. Its positions are numbered from $1$ to $n$.

He wants to modify his string so that every its prefix of even length has an equal amount of letters 'a' and 'b'. To achieve that, Nikolay can perform the following operation arbitrary number of times (possibly, zero): choose some position in his string and replace the letter on this position with the other letter (i.e. replace 'a' with 'b' or replace 'b' with 'a'). Nikolay can use no letters except 'a' and 'b'.

The prefix of string $s$ of length $l$ ($1 \le l \le n$) is a string $s[1..l]$.

For example, for the string $s=$"abba" there are two prefixes of the even length. The first is $s[1\dots2]=$"ab" and the second $s[1\dots4]=$"abba". Both of them have the same number of 'a' and 'b'.

Your task is to calculate the minimum number of operations Nikolay has to perform with the string $s$ to modify it so that every its prefix of even length has an equal amount of letters 'a' and 'b'.


-----Input-----

The first line of the input contains one even integer $n$ $(2 \le n \le 2\cdot10^{5})$ — the length of string $s$.

The second line of the input contains the string $s$ of length $n$, which consists only of lowercase Latin letters 'a' and 'b'.


-----Output-----

In the first line print the minimum number of operations Nikolay has to perform with the string $s$ to modify it so that every its prefix of even length has an equal amount of letters 'a' and 'b'.

In the second line print the string Nikolay obtains after applying all the operations. If there are multiple answers, you can print any of them.


-----Examples-----
Input
4
bbbb

Output
2
abba

Input
6
ababab

Output
0
ababab

Input
2
aa

Output
1
ba



-----Note-----

In the first example Nikolay has to perform two operations. For example, he can replace the first 'b' with 'a' and the last 'b' with 'a'. 

In the second example Nikolay doesn't need to do anything because each prefix of an even length of the initial string already contains an equal amount of letters 'a' and 'b'.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has two binary strings A and B, each of length N.

Chef can rearrange both the strings in any way. Find the maximum [bitwise XOR] he can achieve if he rearranges the strings optimally.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines:
- The first line of each test case contains binary string A.
- The second line of each test case contains binary string B.

------ Output Format ------ 

For each test case, output the maximum bitwise XOR of the strings in binary representation.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 5 \cdot 10^{5}$
- Strings $A$ and $B$ consist only of $0$ and $1$.
- The sum of $N$ over all test cases do not exceed $5 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
0011
1011
100
100
11111
11101
1
0

----- Sample Output 1 ------ 
1110
110
10000
1

----- explanation 1 ------ 
Test case $1$: Rearranging string $A$ as $0011$ and string $B$ as $1101$, the XOR of the strings is $0011\oplus 1101 = 1110$. It can be shown that this is the maximum XOR that can be achieved by rearranging the strings.

Test case $2$: Rearranging string $A$ as $010$ and string $B$ as $100$, the XOR of the strings is $010\oplus 100 = 110$. It can be shown that this is the maximum XOR that can be achieved by rearranging the strings.

Test case $3$: Rearranging string $A$ as $11111$ and string $B$ as $01111$, the XOR of the strings is $11111\oplus 01111 = 10000$. It can be shown that this is the maximum XOR that can be achieved by rearranging the strings.

Test case $4$: Rearranging string $A$ as $1$ and string $B$ as $0$, the XOR of the strings is $1\oplus 0 = 1$. It can be shown that this is the maximum XOR that can be achieved by rearranging the strings.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
## Task

Write a method `remainder` which takes two integer arguments, `dividend` and `divisor`, and returns the remainder when dividend is divided by divisor. Do NOT use the modulus operator (%) to calculate the remainder!

#### Assumption

Dividend will always be `greater than or equal to` divisor.

#### Notes

Make sure that the implemented `remainder` function works exactly the same as the `Modulus operator (%)`.

```if:java
`SimpleInteger` is a tiny and immutable implementation of an integer number. Its interface is a very small subset of the `java.math.BigInteger` API:

* `#add(SimpleInteger val)`
* `#subtract(SimpleInteger val)`
* `#multiply(SimpleInteger val)`
* `#divide(SimpleInteger val)`
* `#compareTo(SimpleInteger val)`
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows:

Eat one orange.
If the number of remaining oranges (n) is divisible by 2 then you can eat  n/2 oranges.
If the number of remaining oranges (n) is divisible by 3 then you can eat  2*(n/3) oranges.

You can only choose one of the actions per day.
Return the minimum number of days to eat n oranges.
 
Example 1:
Input: n = 10
Output: 4
Explanation: You have 10 oranges.
Day 1: Eat 1 orange,  10 - 1 = 9.  
Day 2: Eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3. (Since 9 is divisible by 3)
Day 3: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. 
Day 4: Eat the last orange  1 - 1  = 0.
You need at least 4 days to eat the 10 oranges.

Example 2:
Input: n = 6
Output: 3
Explanation: You have 6 oranges.
Day 1: Eat 3 oranges, 6 - 6/2 = 6 - 3 = 3. (Since 6 is divisible by 2).
Day 2: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. (Since 3 is divisible by 3)
Day 3: Eat the last orange  1 - 1  = 0.
You need at least 3 days to eat the 6 oranges.

Example 3:
Input: n = 1
Output: 1

Example 4:
Input: n = 56
Output: 6

 
Constraints:

1 <= n <= 2*10^9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We are given a 2-dimensional grid. "." is an empty cell, "#" is a wall, "@" is the starting point, ("a", "b", ...) are keys, and ("A", "B", ...) are locks.
We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions.  We cannot walk outside the grid, or walk into a wall.  If we walk over a key, we pick it up.  We can't walk over a lock unless we have the corresponding key.
For some 1 <= K <= 6, there is exactly one lowercase and one uppercase letter of the first K letters of the English alphabet in the grid.  This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.
Return the lowest number of moves to acquire all keys.  If it's impossible, return -1.
 

Example 1:
Input: ["@.a.#","###.#","b.A.B"]
Output: 8


Example 2:
Input: ["@..aA","..B#.","....b"]
Output: 6


 
Note:

1 <= grid.length <= 30
1 <= grid[0].length <= 30
grid[i][j] contains only '.', '#', '@', 'a'-'f' and 'A'-'F'
The number of keys is in [1, 6].  Each key has a different letter and opens exactly one lock.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef wants to select a subset $S$ of the set $\{1, 2, \ldots, N\}$ such that there are no two integers $x, y \in S$ which satisfy $\frac{x}{y} = M$.
Help Chef find the maximum size of a subset $S$ he can choose and the number of ways in which he can choose a subset $S$ with this maximum size. Since the number of ways to choose $S$ can be very large, calculate it modulo $998,244,353$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $N$ and $M$.

-----Output-----
For each test case, print a single line containing two space-separated integers ― the maximum size of a subset Chef can choose and the number of ways to choose a subset with this maximum size modulo $998,244,353$. Note that only the number of ways to choose a subset should be printed modulo $998,244,353$.

-----Constraints-----
- $1 \le T \le 10,000$
- $2 \le M \le N \le 10^{18}$

-----Example Input-----
3
5 2
10 2
100 3

-----Example Output-----
4 1
6 12
76 49152

-----Explanation-----
Example case 1: The only subset $S$ with the maximum size which Chef can choose is $\{1, 3, 4, 5\}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Everybody knows that Balázs has the fanciest fence in the whole town. It's built up from N fancy sections. The sections are rectangles standing closely next to each other on the ground. The ith section has integer height h_i and integer width w_i. We are looking for fancy rectangles on this fancy fence. A rectangle is fancy if: 

  * its sides are either horizontal or vertical and have integer lengths 
  * the distance between the rectangle and the ground is integer 
  * the distance between the rectangle and the left side of the first section is integer 
  * it's lying completely on sections 

What is the number of fancy rectangles? This number can be very big, so we are interested in it modulo 10^9+7.

Input

The first line contains N (1≤ N ≤ 10^{5}) – the number of sections. The second line contains N space-separated integers, the ith number is h_i (1 ≤ h_i ≤ 10^{9}). The third line contains N space-separated integers, the ith number is w_i (1 ≤ w_i ≤ 10^{9}).

Output

You should print a single integer, the number of fancy rectangles modulo 10^9+7. So the output range is 0,1,2,…, 10^9+6.

Scoring

 \begin{array}{|c|c|c|} \hline Subtask & Points & Constraints \\\ \hline 1 & 0 & sample\\\ \hline 2 & 12 & N ≤ 50 \: and \: h_i ≤ 50 \: and \: w_i = 1 \: for all \: i \\\ \hline 3 & 13 & h_i = 1 \: or \: h_i = 2 \: for all \: i \\\ \hline 4 & 15 & all \: h_i \: are equal \\\ \hline 5 & 15 & h_i ≤ h_{i+1} \: for all \: i ≤ N-1 \\\ \hline 6 & 18 & N ≤ 1000\\\ \hline 7 & 27 & no additional constraints\\\ \hline \end{array} 

Example

Input


2
1 2
1 2


Output


12

Note

The fence looks like this: <image>

There are 5 fancy rectangles of shape: <image>

There are 3 fancy rectangles of shape: <image>

There is 1 fancy rectangle of shape: <image>

There are 2 fancy rectangles of shape: <image>

There is 1 fancy rectangle of shape: <image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Squirrel Liss lived in a forest peacefully, but unexpected trouble happens. Stones fall from a mountain. Initially Squirrel Liss occupies an interval [0, 1]. Next, n stones will fall and Liss will escape from the stones. The stones are numbered from 1 to n in order.

The stones always fall to the center of Liss's interval. When Liss occupies the interval [k - d, k + d] and a stone falls to k, she will escape to the left or to the right. If she escapes to the left, her new interval will be [k - d, k]. If she escapes to the right, her new interval will be [k, k + d].

You are given a string s of length n. If the i-th character of s is "l" or "r", when the i-th stone falls Liss will escape to the left or to the right, respectively. Find the sequence of stones' numbers from left to right after all the n stones falls.


-----Input-----

The input consists of only one line. The only line contains the string s (1 ≤ |s| ≤ 10^6). Each character in s will be either "l" or "r".


-----Output-----

Output n lines — on the i-th line you should print the i-th stone's number from the left.


-----Examples-----
Input
llrlr

Output
3
5
4
2
1

Input
rrlll

Output
1
2
5
4
3

Input
lrlrr

Output
2
4
5
3
1



-----Note-----

In the first example, the positions of stones 1, 2, 3, 4, 5 will be $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{3}{16}, \frac{5}{32}$, respectively. So you should print the sequence: 3, 5, 4, 2, 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.