Codechef 2019 Challenge java solutions

January Challenge

Chef and Modulo Game

https://www.codechef.com/problems/MGAME

Chef is playing a game with two of his friends. In this game, each player chooses an integer between 11 and PP inclusive. Let’s denote the integers chosen by Chef, friend 1 and friend 2 by ii, jj and kk respectively; then, Chef’s score is(((Nmodi)modj)modk)modN.(((Nmodi)modj)modk)modN.

Chef wants to obtain the maximum possible score. Let’s denote this maximum score by MM. Find the number of ways to choose the triple (i,j,k)(i,j,k) so that Chef’s score is equal to MM.

Input

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first and only line of each test case contains two space-separated integers NN and PP.

Output

For each test case, print a single line containing one integer — the number of ways to obtain the maximum score.

Constraints

• 1≤T≤1061≤T≤106
• 1≤N≤P≤1061≤N≤P≤106

Subtasks

Subtask #1 (10 points):

• 1≤T≤1001≤T≤100
• 1≤N≤P≤1001≤N≤P≤100

Subtask #2 (90 points): original constraints

Example Input

2 4 4 3 4

Example Output

9 13

Explanation

Example case 1: Chef’s maximum possible score is M=1M=1. All possible values of (i,j,k)(i,j,k) such that the score is 11 are (3,2,2)(3,2,2), (3,2,3)(3,2,3), (3,2,4)(3,2,4), (3,3,2)(3,3,2), (3,3,3)(3,3,3), (3,3,4)(3,3,4), (3,4,2)(3,4,2), (3,4,3)(3,4,3), (3,4,4)(3,4,4).

Solution:

/* package codechef; // don’t place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here

BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

int t1 = Integer.parseInt(r.readLine());

while(t1– > 0)
{
String k = r.readLine();
String data[] = k.split(” “,2);
long n = Long.parseLong(data[0]);
long p = Long.parseLong(data[1]);

// System.out.println(n);
// System.out.println(p);

long m=0;
m= (n-1)/2;
// m= n%((n/2)+1);
long num_ways =0;
//System.out.println(m);
if(n <=2)
System.out.println(p*p*p);
else if(n ==p)
{
// one way to select i which gives max modulous
// j , k can be any value between m & P which will not change modulous

num_ways+= 1 *(p-m) * (p-m);

System.out.println(num_ways);

}
else
{
//case 1
// select i > n , j one way , k will be left with (p-m)
num_ways+= (p-n)*1 * (p-m);

// System.out.println(num_ways);
// case 2

// select i > n , j > n , k=1
num_ways+= (p-n)*(p-n)*1;

// System.out.println(num_ways);

// case 3
// select i=1 , j/k as (p-m)
num_ways += 1* (p-m)*(p-m);

System.out.println(num_ways);
}
}

}
}

February Challenge

Deputy Chef

https://www.codechef.com/FEB19B/problems/DEPCHEF

A battle is going to begin in the kingdom of Airland. There are NN soldiers in the kingdom, numbered 11 through NN and standing in a circle in such a way that for each valid ii, the soldier directly to the right of the ii-th soldier is soldier i+1i+1, and the soldier directly to the right of the NN-th soldier is soldier 11.

Each soldier holds a sword and a shield. The sword is used to attack other soldiers and the shield is used to defend from attacks. Let’s denote the attack value of the ii-th soldier’s sword by aiai and the defense value of the ii-th soldier’s shield by didi.

In the battle, each soldier picks one of the soldiers standing to his left and right, and attacks that soldier. The choices of the soldiers are completely independent, so each soldier can be attacked by the soldier to his left, by the soldier to his right (the power of such an attack is the attack value of the attacking soldier’s sword), by both of them (then, the power of the resulting attack is the sum of the attack values of these soldiers’ swords) or by nobody. A soldier remains alive if the defense value of his shield is strictly greater than the power with which he is attacked. Everyone attacks simultaneously and there is only one round of attacks. Each soldier that remains alive at the end is awarded a laurel.

The king of Airland likes these fights, so the host of the battle promised the king that he can pick one soldier and if the soldier he picks survives the battle, the king receives the shield of that soldier.

Chef is the deputy of the king and you want to help him pick a soldier for the king in such a way that the king receives the best shield (with the greatest defense value). However, if Chef picks a soldier and that soldier does not survive, Chef will be thrown in a snake pit. Therefore, it should be guaranteed that the chosen soldier will survive regardless of the decisions of the other soldiers.

Can you help Chef make the best choice and tell him the defense value of the shield which the king gets, or decide that he can be thrown in the snake pit no matter which soldier he picks?

Input

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains a single integer NN.
• The second line contains NN space-separated integers a1,a2,…,aNa1,a2,…,aN.
• The third line contains NN space-separated integers d1,d2,…,dNd1,d2,…,dN.

Output

For each test case, print a single line containing one integer ― the best defense value of the shield the king gets, or −1−1 if Chef can be thrown in the snake pit.

Constraints

• 1≤T≤1001≤T≤100
• 3≤N≤1003≤N≤100
• 1≤ai,di≤1041≤ai,di≤104 for each valid ii

Subtasks

Subtask #1 (100 points): original constraints

Example Input

[sourcecode language=”csharp”] 2 4 1 1 4 1 3 4 2 1 7 5 4 5 4 5 4 5 3 2 4 7 2 5 9 [/sourcecode]

Example Output

[sourcecode language=”csharp”] 3 -1 [/sourcecode]

Explanation

Example case 1: Soldier 11 can be attacked by soldier 22 and/or soldier 44. If only soldier 22 attacks him, the power of the attack is 11. If only soldier 44 attacks him, the power of the attack is 11 again. If they attack together, the power of the attack is 22. In each of these cases, soldier 11 will live.

Soldier 22 can be attacked by soldier 33, with attack power 44. His shield has defense value 44, which is not enough, so in this case, soldier 22 would die. The best safe choice is soldier 11, with defense value 33.

Example case 2: No soldier is guaranteed to survive the battle, so the answer is −1.

Solution

[sourcecode language=”java”]

/* package codechef; // don’t place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

import java.util.HashMap;

class DEPCHEF {
public static void main(String[] args) throws java.lang.Exception {
java.io.BufferedReader r = new java.io.BufferedReader(
new java.io.InputStreamReader(System.in));
int t1 = Integer.parseInt(r.readLine().toString());
while (t1– > 0) {
int n = Integer.parseInt(r.readLine().toString());
HashMap<character, integer=””> hm = new HashMap<>();
int count = 0;
String k = r.readLine();
String a[] = k.split(” “,n);
String l = r.readLine();
String d[] = l.split(” “,n);
int max = 0;</character,>

// if(Integer.parseInt(d[0]) > Integer.parseInt(a[n-1]) ||
// Integer.parseInt(d[0]) > Integer.parseInt(a[1]) ||
if( Integer.parseInt(d[0]) >(Integer.parseInt(a[n-1]) + Integer.parseInt(a[1])) )
{
if(Integer.parseInt(d[0]) > max)
max = Integer.parseInt(d[0]);

}

for(int i =1 ; i < n ; i++) { // if(Integer.parseInt(d[i]) > Integer.parseInt(a[i-1]) ||
// Integer.parseInt(d[i]) > Integer.parseInt(a[(i+1)%n]) ||
if(Integer.parseInt(d[i]) >(Integer.parseInt(a[i-1]) + Integer.parseInt(a[(i+1)%n])) )
{
if(Integer.parseInt(d[i]) > max)
max = Integer.parseInt(d[i]);

}
}
if(max !=0)
System.out.println(max);
else
System.out.println(-1);
}
}
}

[/sourcecode]

Appy and Contest 

Appy and Chef are participating in a contest. There are NN problems in this contest; each problem has a unique problem code between 11 and NN inclusive. Appy and Chef decided to split the problems to solve between them ― Appy should solve the problems whose problem codes are divisible by AA but not divisible by BB, and Chef should solve the problems whose problem codes are divisible by BB but not divisible by AA (they decided to not solve the problems whose codes are divisible by both AA and BB).

To win, it is necessary to solve at least KK problems. You have to tell Appy whether they are going to win or lose.

Input

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first and only line of each test case contains four space-separated integers NN, AA, BB and KK.

Output

For each test case, print a single line containing the string "Win" if they can solve at least KK problems or "Lose" otherwise (without quotes).

Constraints

• 1≤T≤151≤T≤15
• 1≤K≤N≤10181≤K≤N≤1018
• 1≤A,B≤1091≤A,B≤109

Subtasks

Subtask #1 (15 points):

• 1≤T≤151≤T≤15
• 1≤K≤N≤1061≤K≤N≤106
• 1≤A,B≤1031≤A,B≤103

Subtask #2 (85 points): original constraints

Example Input

[sourcecode language=”java”]

1 6 2 3 3

[/sourcecode]

Example Output

[sourcecode language=”java”]
Win
[/sourcecode]

Explanation

Example case 1: Appy is solving the problems with codes 22 and 44, Chef is solving the problem with code 33. Nobody is solving problem 66, since 66 is divisible by both 22and 33. Therefore, they can solve 33 problems and win.

Solution in java :

[sourcecode language=”java”]
/* package codechef; // don’t place package name! */
import java.util.; import java.lang.;
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;

class HMAPPY2 {
static int i=1;
public static BigInteger lcm(String a, String b)
{
// convert string ‘a’ and ‘b’ into BigInteger
BigInteger s = new BigInteger(a);
BigInteger s1 = new BigInteger(b);

// calculate multiplication of two bigintegers
BigInteger mul = s.multiply(s1);

// calculate gcd of two bigintegers
BigInteger gcd = s.gcd(s1);

// calculate lcm using formula: lcm * gcd = x * y
BigInteger lcm = mul.divide(gcd);
return lcm;

public static void main(String[] args) throws java.lang.Exception {
java.io.BufferedReader r = new java.io.BufferedReader(
new java.io.InputStreamReader(System.in));
int t1 = Integer.parseInt(r.readLine().toString());
while (t1– > 0)

{

String k = r.readLine();
i=1;
String a[] = k.split(” “, 4);
BigInteger b = new BigInteger(a[0]).divide(new BigInteger(a[1]));
BigInteger c = new BigInteger(a[0]).divide(new BigInteger(a[2]));
BigInteger d = new BigInteger(a[0]).divide(lcm(a[1],(a[2])));

BigInteger e = b.add(c).subtract(d.multiply(new BigInteger(“2”)));
if(e.subtract(new BigInteger(a[3])).compareTo(new BigInteger(“0”))== 0 ||
e.subtract(new BigInteger(a[3])).compareTo(new BigInteger(“0”))== 1)
System.out.println(“Win”);
else
System.out.println(“Lose”);

}

}

}

}

[/sourcecode]

Expression Processor :

import java.io.*;
import java.lang.reflect.Type;
import java.text.ParseException;
import java.util.*;
import com.google.gson.Gson;
import com.google.gson.reflect.TypeToken;
import org.json.JSONObject;

//[“AND”,
// {“var1” : “value1”},
// [“OR”,
// { “var2” : “value2” },
// { “var3” : “value3” }
// ]
// ]

public class ExP {
// The function can be extended for n number of oprtators
public static String performOp(String optr , String s1 , String s2)
{
if(optr.equals(“AND”))
{
Boolean b = Boolean.parseBoolean(s1) && Boolean.parseBoolean(s2);
return b.toString() ;
}
else{ //OR operator
Boolean b = Boolean.parseBoolean(s1) || Boolean.parseBoolean(s2);
return b.toString() ;

}
}

public static String transform( Map expMap)
{
Stack orandS = new Stack<>();
for(String optr : expMap.keySet()) //oprator is always key
{
Object jA=expMap.get(optr);
for(int i=0 ; i <((ArrayList)jA).size();i++) { Object s= ((ArrayList)jA).get(i); // Instead of boolean , conditions like x > y can be given,
// for that cdde can be modifed
if(s.toString().equals(“true”) || s.toString().equals(“false”))
{
if(orandS.size() > 0 ) {
String s1= orandS.peek();
orandS.pop();
orandS.push(performOp(optr,s.toString(),s1));
}
else
orandS.push(s.toString());
}
else
{
Gson gson = new Gson();
Type type = new TypeToken>(){}.getType();
Map myMap = gson.fromJson(s.toString(), type);

orandS.push(transform(myMap));

}

}

}
return orandS.peek();
}

public static void pritnt(String jsonObject) throws IOException, ParseException {
// Parse a JsonObject into a JSON string
StringWriter stringWriter = new StringWriter();
String json = “”;
Reader inputString = new StringReader(jsonObject);
BufferedReader br = new BufferedReader(inputString);
String line;
StringBuilder builder=new StringBuilder();
while ((line = br.readLine()) != null) {
builder.append(line);

}
Gson gson = new Gson();
Type type = new TypeToken>(){}.getType();
Map myMap = gson.fromJson(builder.toString(), type);

Map ob = (Map ) myMap.get(“e”);
// Parse a JSON string into a JsonNode
JSONObject js = new JSONObject(jsonObject);
Iterator keys = js.keys();
StackoprS = new Stack<>();
StackorandS=new Stack<>();

while(keys.hasNext()) {
String key = keys.next();
Object jso= js.get(key);
Map expMap = gson.fromJson(jso.toString(), type);
System.out.println(transform(expMap));

}

}

public static void main (String[] args) throws ParseException,IOException
{

// Code can be modified to check x > 7 instead of sample boolean values
// String jo = “{\n” +
// “\t\”e\”: {\n” +
// “\t\t\”AND\”: [\”x > y\”,\n” +
// “\t\t\t\”y > 7 \”,\n” +
// “\t\t\t{\n” +
// “\t\t\t\t\”OR\”: [\”x > y\”,\n” +
// “\t\t\t\t\t\”y > 7 \”\n” +
// “\t\t\t\t]\n” +
// “\t\t\t}\n” +
// “\n” +
// “\t\t]\n” +
// “\n” +
// “\t}\n” +
// “}”;
// Can be mock tested for any level of nesting
String jo = “{\n” +
“\t\”e\”: {\n” +
“\t\t\”AND\”: [\”true\”, \”true\”,\n” +
“\t\t\t{\n” +
“\t\t\t\t\”OR\”: [\”false\”, \”false\”]\n” +
“\t\t\t}\n” +
“\t\t]\n” +
“\t}\n” +
“}”;
pritnt(jo);
}
}

Chef and a Beautiful Digit Problem Code: CHDIGER

Chef Leonardo has a decimal integer NN and a non-zero decimal digit dd. NN does not contain the digit zero; specifically, NN should always be treated as a decimal integer without leading zeroes.

Chef likes dd and does not like any other digit, so he decided to change NN. He may apply the following operation any number of times (including zero): append the digit dd to the decimal representation of NN (dd becomes the least significant digit of NN), then remove one occurrence of one digit from the decimal representation of NN.

Chef has already changed a lot of numbers and he got bored. Now, he wants to know the smallest possible value of NN which can be obtained by performing the operation described above. Can you help him?

Input

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first and only line of each test case contains two space-separated integers NN and dd.

Output

For each test case, print a single line containing one integer – the minimum number Chef can obtain.

Constraints

• 1≤T≤1,0001≤T≤1,000
• 1≤N≤10181≤N≤1018
• NN does not contain the digit 00
• 1≤d≤91≤d≤9

Subtasks

Subtask #1 (40 points):

• 1≤T≤1001≤T≤100
• 1≤N≤1091≤N≤109

Subtask #2 (60 points): original constraints

Example Input

3 35 4 42 4 24 9

Example Output

34 24 24

Solution:

class CHDIGER {

static void GetMinString(String orig,String data ,int d ,int orig_length)
{
int index=data.charAt(0);
char maxi=data.charAt(0);
StringBuilder myName = new StringBuilder(data);
if(data.length() > 1) {
for (int i = 1; i < myName.length(); i++) { if ( (myName.charAt(i)) < maxi) { maxi = (myName.charAt(i)); index = i; } } } if(Character.getNumericValue(maxi) > d)
{
StringBuilder s = new StringBuilder(orig);
for(int i=0 ; i < orig_length-orig.length();i++)
s.append(String.valueOf(d));
System.out.println(s);

}

else {

int count=0;

for (int i = 0; i < myName.length(); i++) {

if ( (myName.charAt(i))==maxi) {

count++;

}

}

StringBuilder sb = new StringBuilder(orig);

for (int i = 0; i < count; i++) {

sb.append(maxi);

}

StringBuilder s = new StringBuilder(myName.substring (myName.lastIndexOf(String.valueOf(maxi))+1));

if(s.length()!=0) GetMinString(sb.toString(),s.toString(),d,orig_length);

else {

for(int i=0 ; i < orig_length-count-orig.length();i++) sb.append(d);

System.out.println(sb);

}

}

}

public static void main (String[] args) throws java.lang.Exception { java.io.BufferedReader r = new java.io.BufferedReader ( new java.io.InputStreamReader (System.in));

Long t1 =Long.parseLong(r.readLine().toString());

Long max , min;

while(t1– > 0) {

String data[] = r.readLine().split(” “, 2);

int d = Integer.parseInt(data[1]); GetMinString(“”,data[0],d,data[0].length());

}
}
}

April Challenge

FENCING

https://www.codechef.com/APRIL19B/problems/FENCE

There is a field with plants — a grid with NN rows (numbered 11 through NN) and MMcolumns (numbered 11 through MM); out of its NMNM cells, KK cells contain plants, while the rest contain weeds. Two cells are adjacent if they have a common side.

You want to build fences in the field in such a way that the following conditions hold for each cell that contains a plant:

• it is possible to move from this cell to each adjacent cell containing a plant without crossing any fences
• it is impossible to move from this cell to any cell containing weeds or to leave the grid without crossing any fences

The fences can only be built between cells or on the boundary of the grid, i.e. on the sides of cells. The total length of the built fences is the number of pairs of side-adjacent cells such that there is a fence built on their common side plus the number of sides of cells on the boundary of the grid which have fences built on them. Find the minimum required total length of fences that need to be built.

Input

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains three space-separated integers NN, MMand KK.
• KK lines follow. Each of these lines contains two space-separated integers rrand cc denoting that the cell in row rr and column cc contains a plant.

Output

For each test case, print a single line containing one integer — the minimum required length of fences.

Constraints

• 1≤T≤101≤T≤10
• 1≤N,M≤1091≤N,M≤109
• 1≤K≤1051≤K≤105
• 1≤r≤N1≤r≤N
• 1≤c≤M1≤c≤M
• the cells containing plants are pairwise distinct

Subtasks

Subtask #1 (30 points): 1≤N,M≤1,0001≤N,M≤1,000

Subtask #2 (70 points): original constraints

Example Input

2 4 4 9 1 4 2 1 2 2 2 3 3 1 3 3 4 1 4 2 4 3 4 4 1 1 1

Example Output

20 4

Explanation

Example case 1: The field looks like this (‘x’ denotes a cell containing a plant, ‘.’ denotes a cell containing weeds):

…x xxx. x.x. xxx.

An optimal solution is to build fences around the topmost plant (with length 44), around the remaining eight plants (with length 1212) and around the hole between them (with length 44). The total length is 4+12+4=204+12+4=20.

Solution:

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.io.*;
import java.util.*;

class Pair {
int x;
int y;

// Constructor
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Pair)) return false;
Pair key = (Pair) o;
return x == key.x && y == key.y;
}

@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}
}

class Compare {

static void compare(Pair arr[], int n)
{
// Comparator to sort the pair according to second element
Arrays.sort(arr, new Comparator<Pair>() {
@Override public int compare(Pair p1, Pair p2)
{
return p1.y – p2.y;
}
});

for (int i = 0; i < n; i++) {
System.out.print(arr[i].x + ” ” + arr[i].y + ” “);
}
System.out.println();
}
}
public class FENCE {

// Check if cell (x, y) is valid or not
private static boolean isValidCell(int x, int y,int N ,int M)
{
if (x < 0 || y < 0 || x >= N || y >= M)
return false;

return true;
}

public static void main (String[] args) throws java.lang.Exception {
java.io.BufferedReader s = new java.io.BufferedReader(
new java.io.InputStreamReader(System.in));
Integer t = Integer.parseInt(s.readLine().toString());

while(t– > 0) {
String data[] = s.readLine().split(” “, 3);
int n = Integer.parseInt(data[0]);
int m = Integer.parseInt(data[1]);
int k = Integer.parseInt(data[2]);
//Store in map instead of matrix to avoid space usage
Map<Pair, Integer> map = new HashMap<>();
Pair arr[] = new Pair[k];

//Loop for k , as N is very large
for(int i=0 ; i < k;i++)
{
String data1[] = s.readLine().split(” “, 2);
int r = Integer.parseInt(data1[0])-1;
int c = Integer.parseInt(data1[1])-1;
//maze[r][c]=1;
arr[i] = new Pair(r, c);
map.put(new Pair(r, c),1);
}
long count=0;

Arrays.sort(arr, new Comparator<Pair>() {
@Override public int compare(Pair p1, Pair p2)
{
return p1.y – p2.y;
}
});

for(int l=0 ; l < arr.length;l++)
{
int i=arr[l].x;
int j=arr[l].y;
Pair p = new Pair(arr[l].x,arr[l].y);
if(i==0 && map.containsKey(p))
count++;
if(j==0 && map.containsKey(p))
count++;

if(map.containsKey(p))
{
if(isValidCell(i+1 , j,n,m))
{
if(!map.containsKey(new Pair(arr[l].x+1,arr[l].y)))
count++;

}
else
count++;
if(isValidCell(i , j+1,n,m))
{
if(!map.containsKey(new Pair(arr[l].x,arr[l].y+1)))
count++;


}
else
count++;
if(isValidCell(i-1 , j,n,m))
{
if(map.containsKey(new Pair(arr[l].x,arr[l].y)) &&
!map.containsKey(new Pair(arr[l].x-1,arr[l].y)) )
count++;


}
if(isValidCell(i , j-1,n,m))
{
if(map.containsKey(new Pair(arr[l].x,arr[l].y)) &&
!map.containsKey(new Pair(arr[l].x,arr[l].y-1)))
count++;


}
}
}
System.out.println(count);
}
}
}

Minimum and Maximum 

Chef has KK chocolates and he wants to distribute them to NN people (numbered 11through NN). These people are standing in a line in such a way that for each ii (1≤i≤N−11≤i≤N−1), person ii and person i+1i+1 are adjacent.

First, consider some way to distribute chocolates such that for each valid ii, the number of chocolates the ii-th person would receive from Chef is AiAi and the sum S1=∑N−1i=1|Ai−Ai+1|S1=∑i=1N−1|Ai−Ai+1| is minimum possible. Of course, each person must receive a non-negative integer number of chocolates.

Then, Chef wants to create a new sequence B1,B2,…,BNB1,B2,…,BN by rearranging (permuting) the elements of the sequence A1,A2,…,ANA1,A2,…,AN. For each valid ii, the number of chocolates the ii-th person actually receives from Chef is BiBi. Chef wants to distribute the chocolates (choose B1,B2,…,BNB1,B2,…,BN by permuting the sequence AAand give BiBi chocolates to the ii-th person for each valid ii) in such a way that S2=∑N−1i=1|Bi–Bi+1|S2=∑i=1N−1|Bi–Bi+1| is maximum possible. You need to find the maximum value of S2S2.

It is guaranteed that S2S2 does not depend on the exact choice of the sequence A1,A2,…,ANA1,A2,…,AN, as long as it is a sequence that minimises S1S1.

Solution

include <iostream>

using namespace std;

include “bits/stdc .h”

int longDivision(string number, int divisor)
{
// As result can be very large store it in string
string ans;

// Find prefix of number that is larger
// than divisor.
int idx = 0;
int temp = number[idx] - '0';
while (temp < divisor)
    temp = temp * 10   (number[  idx] - '0');

// Repeatedly divide divisor with temp. After
// every division, update temp to include one
// more digit.
while (number.size() > idx)
{
    // Store result in answer i.e. temp / divisor
    ans  = (temp / divisor)   '0';

    // Take next digit of number
    if(number.size() ==idx 1){
        temp = (temp % divisor);
        idx  ;
    }
    else
        temp = (temp % divisor) * 10   number[  idx] - '0';
}

if (ans.length() == 0)
    return -1;

// else return ans
return temp;
}

int main() {

string sss;

int ttt;

getline(cin, sss);

stringstream ss;

//ss << s;

ttt=stoi(sss);

while ( ttt– ) { int n = 0, c = 0; getline(cin, sss);

n = stoi(sss); getline(cin, sss); //c=stoi(sss); //cout << sss<< endl; //vector<int> v;

int rem = 0; rem = longDivision(sss, n);

//If divisor is greater then number

if(rem==-1) { rem=stoi(sss); }

if (rem == 0) cout << 0 << endl;

else {

// whichever is lower in count( 0 or 1 ) ,arrang in order 0 1 0 1 0 or 1 0 1 0 1 for max , so its 2 times count

but if both 0 and 1 are equal it would become two times -1 as 010101 or 101010

if (rem > n / 2) { rem=n- rem; }

if(n==2){ cout <<“1”; }else {

if(n%2 ==0 && rem==n/2)

cout << 2*rem -1 << endl;

else

cout << 2 * rem << endl; } } } return 0;

}