GeeksForGeeks/sudo placement 2019.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "5\n",
      "4 2 1 5 3\n",
      "2 1 -1 3 -1\n",
      "6\n",
      "5 6 2 3 1 7\n",
      "-1 2 -1 1 -1 -1\n"
     ]
    }
   ],
   "source": [
    "#immediate smaller element -----> AMAZON\n",
    "#marks = 1, difficulty = Basic\n",
    "'''\n",
    "Given an integer array of size N. For each element in the array, check whether the right adjacent element (on the next immediate position) of the array is smaller. If next element is smaller, print that element. If not, then print -1.\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. T testcases follow. Each testcase contains 2 lines of input:\n",
    "The first line contains an integer N, where N is the size of array.\n",
    "The second line contains N integers(elements of the array) sperated with spaces.\n",
    "\n",
    "Output:\n",
    "For each test case, print the next immediate smaller elements for each element in the array.\n",
    "\n",
    "Constraints:\n",
    "1 ≤ T ≤ 200\n",
    "1 ≤ N ≤ 107\n",
    "1 ≤ arr[i] ≤ 1000\n",
    "\n",
    "Example:\n",
    "Input\n",
    "2\n",
    "5\n",
    "4 2 1 5 3\n",
    "6\n",
    "5 6 2 3 1 7\n",
    "\n",
    "Output\n",
    "2 1 -1 3 -1\n",
    "-1 2 -1 1 -1 -1\n",
    "\n",
    "Explanation:\n",
    "Testcase 1: Array elements are 4, 2, 1, 5, 3. Next to 4 is 2 which is smaller, so we print 2. Next of 2 is 1 which is smaller, so we print 1. Next of 1 is 5 which is greater, so we print -1. Next of 5 is 3 which is smaller so we print 3.  Note that for last element, output is always going to be -1 because there is no element on right.\n",
    "'''\n",
    "n=int(input())\n",
    "for i in range(n):\n",
    "    m=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    for j in range(m-1):\n",
    "        if j<m-1:\n",
    "            if a[j]>a[j+1]:\n",
    "                print(a[j+1],end=' ')\n",
    "            else:\n",
    "                print(-1,end=' ')\n",
    "    else:\n",
    "        print(-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "5\n",
      "1 2 3 4 5\n",
      "2\n",
      "3 4 5 1 2 \n",
      "1\n",
      "5\n",
      "1\n",
      "5 \n"
     ]
    }
   ],
   "source": [
    "#rotating an array --->  Codenation\n",
    "#marks = 1, difficulty = Basic\n",
    "'''\n",
    "Given an array of N size. The task is to rotate array by d elements where d is less than or equal to N.\n",
    "\n",
    "Input:\n",
    "The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consist of three lines. The first line of each test case consists of an integer N, where N is the size of array.\n",
    "The second line of each test case contains N space separated integers denoting array elements. The third line of each test case contains \"d\" .\n",
    "\n",
    "Output:\n",
    "Corresponding to each test case, in a new line, print the modified array.\n",
    "\n",
    "Constraints:\n",
    "1 ≤ T ≤ 200\n",
    "1 ≤ N ≤ 200\n",
    "1 ≤ A[i] ≤ 1000\n",
    "\n",
    "Example:\n",
    "Input\n",
    "1\n",
    "5\n",
    "1 2 3 4 5\n",
    "2\n",
    "\n",
    "Output\n",
    "3 4 5 1 2\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    m=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    d=int(input())\n",
    "    for j in range(m-d):\n",
    "        print(a[j+d],end=' ')\n",
    "    for j in range(d):\n",
    "        print(a[j],end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "5 2\n",
      "1 2 3 4 5\n",
      "3 4 5 1 2 \n",
      "10 3\n",
      "2 4 6 8 10 12 14 16 18 20\n",
      "8 10 12 14 16 18 20 2 4 6 \n"
     ]
    }
   ],
   "source": [
    "# Rotate Array ---> Amazon,MAQ Software\n",
    "# Difficulty: Basic   Marks: 1\n",
    "'''\n",
    "Given an unsorted array arr[] of size N, rotate it by D elements (clockwise). \n",
    "\n",
    "Input:\n",
    "The first line of the input contains T denoting the number of testcases. First line of eacg test case contains two space separated elements, N denoting the size of the array and an integer D denoting the number size of the rotation. Subsequent line will be the N space separated array elements.\n",
    "\n",
    "Output:\n",
    "For each testcase, in a new line, output the rotated array.\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 200\n",
    "1 <= N <= 107\n",
    "1 <= D <= N\n",
    "0 <= arr[i] <= 105\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "5 2\n",
    "1 2 3 4 5 \n",
    "10 3\n",
    "2 4 6 8 10 12 14 16 18 20\n",
    "\n",
    "Output:\n",
    "3 4 5 1 2\n",
    "8 10 12 14 16 18 20 2 4 6\n",
    "\n",
    "Explanation :\n",
    "Testcase 1: 1 2 3 4 5  when rotated by 2 elements, it becomes 3 4 5 1 2.\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    m,d=tuple(map(int,(input().split())))\n",
    "    a=list(map(int,input().split()))\n",
    "    for j in range(m-d):\n",
    "        print(a[j+d],end=' ')\n",
    "    for j in range(d):\n",
    "        print(a[j],end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "6\n",
      "16 17 4 3 5 2\n",
      "17 5 2 \n",
      "5\n",
      "1 2 3 4 0\n",
      "4 0 \n",
      "5\n",
      "7 4 5 7 3\n",
      "7 7 3 \n"
     ]
    }
   ],
   "source": [
    "# Leaders in an array ---> Amazon, Payu, Samsung\n",
    "# Difficulty: Easy   Marks: 2\n",
    "'''\n",
    "Given an array of positive integers. Your task is to find the leaders in the array.\n",
    "Note: An element of array is leader if it is greater than or equal to all the elements to its right side. Also, the rightmost element is always a leader. \n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.\n",
    "The first line of each test case contains a single integer N denoting the size of array.\n",
    "The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array.\n",
    "\n",
    "Output:\n",
    "Print all the leaders.\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 100\n",
    "1 <= N <= 107\n",
    "0 <= Ai <= 107\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "3\n",
    "6\n",
    "16 17 4 3 5 2\n",
    "5\n",
    "1 2 3 4 0\n",
    "5\n",
    "7 4 5 7 3\n",
    "Output:\n",
    "17 5 2\n",
    "4 0\n",
    "7 7 3\n",
    "\n",
    "Explanation:\n",
    "Testcase 3: All elements on the right of 7 (at index 0) are smaller than or equal to 7. Also, all the elements of right side of 7 (at index 3) are smaller than 7. And, the last element 3 is itself a leader since no elements are on its right.\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "#     c=a.copy()\n",
    "#     for i in range(len(a)-1):\n",
    "#         for j in range(i+1,len(a)):\n",
    "#             if a[i]<a[j]:\n",
    "#                 c.remove(a[i])\n",
    "#                 break\n",
    "    c=[a[-1]]\n",
    "    for i in range(len(a)-2,-1,-1):\n",
    "        if a[i]>= c[-1]:\n",
    "            c.append(a[i])\n",
    "#     for i in c:\n",
    "#         print(i,end=' ')\n",
    "    print(*(c[::-1]),end='')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "4\n",
      "1 2 3 4\n",
      "4 3 2 1\n"
     ]
    }
   ],
   "source": [
    "# Reverse an array ---> Infosys, Moonfrog Labs\n",
    "#  Difficulty: School   Marks: 0\n",
    "'''\n",
    "Given an array A of size N, print the reverse of it.\n",
    "\n",
    "Input:\n",
    "First line contains an integer denoting the test cases 'T'. T testcases follow. Each testcase contains two lines of input. First line contains N the size of the array A. The second line contains the elements of the array.\n",
    "\n",
    "Output:\n",
    "For each testcase, in a new line, print the array in reverse order.\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 100\n",
    "1 <= N <=100\n",
    "0 <= Ai <= 100\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "1\n",
    "4\n",
    "1 2 3 4\n",
    "Output:\n",
    "4 3 2 1\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    a.reverse()\n",
    "    print(*a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "6 2\n",
      "10 20 30 40 50 60\n",
      "20 10 40 30 60 50 "
     ]
    }
   ],
   "source": [
    "# Reverse array in groups ---> Amazon\n",
    "#  Difficulty: Basic   Marks: 1\n",
    "'''\n",
    "Given an array arr[] of positive integers of size N. Reverse every sub-array of K group elements.\n",
    "\n",
    "Input:\n",
    "The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consist of two lines of input. The first line of each test case consists of an integer N(size of array) and an integer K separated by a space. The second line of each test case contains N space separated integers denoting the array elements.\n",
    "\n",
    "Output:\n",
    "For each test case, print the modified array.\n",
    "\n",
    "Constraints:\n",
    "1 ≤ T ≤ 200\n",
    "1 ≤ N, K ≤ 107\n",
    "1 ≤ A[i] ≤ 1018\n",
    "\n",
    "Example:\n",
    "Input\n",
    "2\n",
    "5 3\n",
    "1 2 3 4 5\n",
    "6 2\n",
    "10 20 30 40 50 60\n",
    "\n",
    "Output\n",
    "3 2 1 5 4\n",
    "20 10 40 30 60 50\n",
    "\n",
    "Explanation:\n",
    "Testcase 1: Reversing groups in size 3, first group consists of elements 1, 2, 3. Reversing this group, we have elements in order as 3, 2, 1.\n",
    "'''\n",
    "from math import ceil\n",
    "for i in range(int(input())):\n",
    "    n,k=map(int,input().split())\n",
    "    arr=list(map(int,input().split()))\n",
    "    arr[:k]=arr[k-1::-1] #i was having a bit difficulty in converting the first group inside the loop\n",
    "    for i in range(1,ceil(float(n)/k)):\n",
    "        arr[k*i:k*i+k]=arr[k*i+k-1:k*i-1:-1]\n",
    "    print(*arr)\n",
    "'''for _ in range(int(input())):\n",
    "    n1,n2=input().split()\n",
    "    a=list(map(int,input().split()))\n",
    "#     if int(n1)%int(n2)!=0:\n",
    "#         n2=int(n1)//int(n2)+1\n",
    "    j=int(n1)//int(n2)\n",
    "    for i in range(j):\n",
    "        c=[]\n",
    "        for k in range(int(n2)*i,int(n2)*(i+1)):\n",
    "            c.append(a[k])\n",
    "        print(*(c[::-1]),end=' ')\n",
    "    print('',*(a[:int(n2)*j-1:-1]),end='',sep=' ')\n",
    "    print()\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "6\n",
      "7 10 4 3 20 15\n",
      "3\n",
      "7\n",
      "5\n",
      "7 10 4 20 15\n",
      "4\n",
      "15\n"
     ]
    }
   ],
   "source": [
    "# Kth smallest element --->  ABCO, Accolite, Amazon, Cisco, Hike, Microsoft, Snapdeal, VMWare\n",
    "#  Difficulty: Medium   Marks: 4\n",
    "'''\n",
    "Given an array arr[] and a number K where K is smaller than size of array, the task is to find the Kth smallest element in the given array. It is given that all array elements are distinct.\n",
    "\n",
    "Expected Time Complexity: O(n)\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T, denoting the number of testcases. Then T test cases follow. Each test case consists of three lines. First line of each testcase contains an integer N denoting size of the array. Second line contains N space separated integer denoting elements of the array. Third line of the test case contains an integer K.\n",
    "\n",
    "Output:\n",
    "Corresponding to each test case, print the kth smallest element in a new line.\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 100\n",
    "1 <= N <= 105\n",
    "1 <= arr[i] <= 105\n",
    "1 <= K <= N\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "6\n",
    "7 10 4 3 20 15\n",
    "3\n",
    "5\n",
    "7 10 4 20 15\n",
    "4\n",
    "\n",
    "Output:\n",
    "7\n",
    "15\n",
    "\n",
    "Explanation:\n",
    "Testcase 1: 3rd smallest element in the given array is 7.\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    i=int(input())\n",
    "    a.sort()\n",
    "    print(a[i-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "5\n",
      "3 1 2 5 4\n",
      "5 3 1 4 2\n"
     ]
    }
   ],
   "source": [
    "# Print an array in Pendulum Arrangement --->  FactSet\n",
    "# Difficulty: Basic   Marks: 1\n",
    "'''\n",
    "Write a program to input a list of n integers in an array and arrange them in a way similar to the to-and-fro movement of a Pendulum.\n",
    "\n",
    "The minimum element out of the list of integers, must come in center position of array. If there are even elements, then minimum element should be moved to (n-1)/2 index (considering that indexes start from 0)\n",
    "The next number (next to minimum) in the ascending order, goes to the right, the next to next number goes to the left of minimum number and it continues like a Pendulum.\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the array. Then next line contains N space separated integers forming the array.\n",
    "\n",
    "Output:\n",
    "Output the array in Pendulum Arrangement.\n",
    "\n",
    "Constraints:\n",
    "1<=T<=500\n",
    "1<=N<=100\n",
    "1<=a[i]<=1000\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "5\n",
    "1 3 2 5 4\n",
    "5\n",
    "11 12 31 14 5\n",
    "\n",
    "Output:\n",
    "5 3 1 2 4\n",
    "31 12 5 11 14\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    a.sort(reverse=True)\n",
    "    if len(a)%2!=0:\n",
    "        print(*(a[::2]),end=' ')\n",
    "    else:\n",
    "        print(*(a[1::2]),end=' ')\n",
    "    print(*(a[-2::-2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "86 41\n",
      "3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 19 21 22 23 24 25 27 28 29 30 31 32 33 34 35 36 39 40 42 43 45 46 47 48 49 50 51 52 53 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 74 75 76 78 79 81 82 84 85 87 88 89 90 91 92 93 95 96 97 98 99 100 101 102\n",
      "42\n"
     ]
    }
   ],
   "source": [
    "# Find the closest number\n",
    "# Difficulty: Basic   Marks: 1\n",
    "'''\n",
    "Given an array of sorted integers. The task is to find the closest value to the given number in array. Array may contain duplicate values.\n",
    "\n",
    "Note: If the difference is same for two values print the value which is greater than the given number.\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. First line of each test case contains two integers N & K and the second line contains N space separated array elements.\n",
    "\n",
    "Output:\n",
    "For each test case, print the closest number in new line.\n",
    "\n",
    "Constraints:\n",
    "1<=T<=100\n",
    "1<=N<=105\n",
    "1<=K<=105\n",
    "1<=A[i]<=105\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "4 4\n",
    "1 3 6 7\n",
    "7 4\n",
    "1 2 3 5 6 8 9\n",
    "\n",
    "Output:\n",
    "3\n",
    "5\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    n1,n2=map(int,input().split())\n",
    "    a=list(map(int,input().split()))\n",
    "    a.append(n2)\n",
    "    a.sort()\n",
    "    for i in range(len(a)):\n",
    "        if a[-1]==n2:\n",
    "            print(a[-2])\n",
    "            break\n",
    "        else:\n",
    "            if a[i]==n2:\n",
    "                if a[i+1]==n2:\n",
    "                    print(n2)\n",
    "                    break\n",
    "                else:\n",
    "                    if abs(n2-a[i+1])==abs(n2-a[i-1]):\n",
    "                        print(a[i+1])\n",
    "                        break\n",
    "                    else:\n",
    "                        if abs(n2-a[i+1])>abs(n2-a[i-1]):\n",
    "                            print(a[i-1])\n",
    "                            break\n",
    "                        else:\n",
    "                            print(a[i+1])\n",
    "                            break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "7\n",
      "1 2 3 5 4 7 10\n",
      "7 5 3 1 2 4 10"
     ]
    }
   ],
   "source": [
    "# Sort in specific order  ---> Microsoft, Zoho\n",
    "# Difficulty: Basic   Marks: 1\n",
    "'''\n",
    "Given an array A of positive integers. Your task is to sort them in such a way that the first part of the array contains odd numbers sorted in descending order, rest portion contains even numbers sorted in ascending order.\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer N denoting the size of the array. The next line contains N space separated values of the array.\n",
    "\n",
    "Output:\n",
    "For each test case in a new line print the space separated values of the modified array.\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 103\n",
    "1 <= N <= 107\n",
    "0 <= Ai <= 1018\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "7\n",
    "1 2 3 5 4 7 10\n",
    "7\n",
    "0 4 5 3 7 2 1\n",
    "\n",
    "Output:\n",
    "7 5 3 1 2 4 10\n",
    "7 5 3 1 0 2 4\n",
    "\n",
    "Explanation:\n",
    "Testcase1: Array elements 7 5 3 1 are odd and sorted in descending order, whereas 2 4 10 are even numbers and sorted in ascending order.\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    a.sort()\n",
    "    odd=[]\n",
    "    even=[]\n",
    "    for i in a:\n",
    "        if i%2==0:\n",
    "            even.append(i)\n",
    "        else:\n",
    "            odd.append(i)\n",
    "    print(*(odd[-1::-1]),end=' ',sep=' ')\n",
    "    print(*(even[::1]),end='\\n',sep=' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "8\n",
      "3 4 1 9 56 7 9 12\n",
      "5\n",
      "6\n",
      "7\n",
      "7 3 2 4 9 12 56\n",
      "3\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# Chocolate Distribution Problem ---> Flipkart\n",
    "#  Difficulty: Easy   Marks: 2\n",
    "'''\n",
    "Given an array A of positive integers of size N, where each value represents number of chocolates in a packet. Each packet can have variable number of chocolates. There are M students, the task is to distribute chocolate packets such that :\n",
    "1. Each student gets one packet.\n",
    "2. The difference between the number of chocolates given to the students having packet with maximum chocolates and student having packet with minimum chocolates is minimum.\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow. Each test case consists of three lines. The first line of each test case contains an integer N denoting the number of packets. Then next line contains N space separated values of the array A denoting the values of each packet. The third line of each test case contains an integer m denoting the no of students.\n",
    "\n",
    "Output:\n",
    "For each test case in a new line print the minimum difference.\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 100\n",
    "1 <=N<= 107\n",
    "1 <= Ai <= 1018\n",
    "1 <= M <= N\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "8\n",
    "3 4 1 9 56 7 9 12\n",
    "5\n",
    "7\n",
    "7 3 2 4 9 12 56\n",
    "3\n",
    "\n",
    "Output:\n",
    "6\n",
    "2\n",
    "\n",
    "Explanation:\n",
    "Testcase 1: The minimum difference between maximum chocolates and minimum chocolates is 9-3=6\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    d=int(input())\n",
    "    a.sort()\n",
    "    min=abs(a[0]-a[d-1])\n",
    "    for i in range(1,len(a)-d+1):\n",
    "        if abs(a[i]-a[d-1+i])<min:\n",
    "            min=abs(a[i]-a[d-1+i])\n",
    "    print(min)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "7\n",
      "100 180 260 310 40 535 695\n",
      "(0 3) (4 6) \n",
      "10\n",
      "23 13 25 29 33 19 34 45 65 67\n",
      "(1 4) (5 9) \n"
     ]
    }
   ],
   "source": [
    "# Stock buy and sell ---> Accolite, Amazon, D-E-Shaw, Directi, Facebook, Flipkart, Goldman Sachs, Hike, Intuit, MakeMyTrip, Microsoft, Morgan Stanley, Ola Cabs, Oracle, Paytm, Pubmatic, Quikr, SalesForce, Samsung, SAP Labs, Sapient, Swiggy, Walmart\n",
    "# Difficulty: Medium   Marks: 4\n",
    "'''\n",
    "The cost of stock on each day is given in an array A[] of size N. Find all the days on which you buy and sell the stock so that in between those days your profit is maximum.\n",
    "\n",
    "Input: \n",
    "First line contains number of test cases T. First line of each test case contains an integer value N denoting the number of days, followed by an array of stock prices of N days. \n",
    "\n",
    "Output:\n",
    "For each testcase, output all the days with profit in a single line. And if there is no profit then print \"No Profit\".\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 100\n",
    "2 <= N <= 103\n",
    "0 <= Ai <= 104\n",
    "\n",
    "Example\n",
    "Input:\n",
    "2\n",
    "7\n",
    "100 180 260 310 40 535 695\n",
    "10\n",
    "23 13 25 29 33 19 34 45 65 67\n",
    "\n",
    "Output:\n",
    "(0 3) (4 6)\n",
    "(1 4) (5 9)\n",
    "\n",
    "Explanation:\n",
    "Testcase 1: We can buy stock on day 0, and sell it on 3rd day, which will give us maximum profit.\n",
    "\n",
    "Note: Output format is as follows - (buy_day sell_day) (buy_day sell_day)\n",
    "For each input, output should be in a single line.\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    min_=[]\n",
    "    max_=[]\n",
    "    c=0\n",
    "    for i in range(len(a)-1):\n",
    "        if c==0:\n",
    "            if a[i]<a[i+1]:\n",
    "                min_.append(i)\n",
    "                c+=1\n",
    "        else:\n",
    "            if a[i]>a[i+1]:\n",
    "                max_.append(i)\n",
    "                c-=1\n",
    "    if len(min_)!=len(max_):\n",
    "        max_.append(len(a)-1)\n",
    "    if len(min_)>0:\n",
    "        for i in range(len(min_)):\n",
    "            print(\"(\",min_[i],\" \",max_[i],\")\",sep=\"\",end=\" \")\n",
    "        print()\n",
    "    else:\n",
    "        print('No Profit')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "4\n",
      "4 2 5 7\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "# Element with left side smaller and right side greater ---> Amazon, Intuit, OYO Rooms, Zoho\n",
    "# Difficulty: Easy   Marks: 2\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    a1=a.copy()\n",
    "    for i in range(len(a)):\n",
    "        for j,k in zip(range(i+1,len(a),1),range(i-1,-1,-1)):\n",
    "            if a[i]>a[j]:\n",
    "                a1.remove(a[i])\n",
    "                break\n",
    "            if a[i]<a[k]:\n",
    "                a1.remove(a[i])\n",
    "                break\n",
    "    else:\n",
    "        for i in a:\n",
    "            if a1[0]>i:\n",
    "                a1.remove(a1[0])\n",
    "        else:\n",
    "            print(a1[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 5, 7]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "7\n",
      "7 13 10 2 3 8 11 12 17 18 19  20\n",
      "12\n"
     ]
    }
   ],
   "source": [
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    a1=a.copy()\n",
    "    for i in range(len(a)):\n",
    "        for j,k in zip(range(i+1,len(a),1),range(i-1,-1,-1)):\n",
    "            if a[i]>a[j]:\n",
    "                a1.remove(a[i])\n",
    "                break\n",
    "            if a[i]<a[k]:\n",
    "                a1.remove(a[i])\n",
    "                break\n",
    "            if a1[0]>a[i]:\n",
    "                a1.remove(a1[0])\n",
    "    else:\n",
    "        if len(a1)==0:\n",
    "            print(-1)\n",
    "        else:\n",
    "            print(a1[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[12, 17, 18, 19, 20]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "ere.ereaas.tge.sdds\n"
     ]
    }
   ],
   "source": [
    "for _ in range(int(input())):\n",
    "    a=input().split('.')\n",
    "    for i in range(len(a)-1,-1,-1):\n",
    "        if i>0:\n",
    "            print(a[i],end='.')\n",
    "        if i==0:\n",
    "            print(a[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['ere', 'ereaas', 'tge', 'sdds']"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sdds.tge.ereaas.ere\n"
     ]
    }
   ],
   "source": [
    "for i in range(len(a)-1,-1,-1):\n",
    "    if i>0:\n",
    "        print(a[i],end='.')\n",
    "    if i==0:\n",
    "        print(a[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "5256575657505256%7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "YX  X  XXY\n"
     ]
    },
    {
     "ename": "NameError",
     "evalue": "name 'isInterleave' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-25-a3cbcb7f325b>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      5\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mt\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m         \u001b[0marr\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0minput\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mstrip\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msplit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m         \u001b[0;32mif\u001b[0m \u001b[0misInterleave\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0marr\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0marr\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0marr\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      8\u001b[0m             \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      9\u001b[0m         \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mNameError\u001b[0m: name 'isInterleave' is not defined"
     ]
    }
   ],
   "source": [
    "\n",
    "# Your code goes here\n",
    "if __name__=='__main__':\n",
    "    t = int(input())\n",
    "    for i in range(t):\n",
    "        arr=input().strip().split()\n",
    "        if isInterleave(arr[0], arr[1], arr[2]):\n",
    "            print(1)\n",
    "        else:\n",
    "            print(0)\n",
    "''' This is a function problem.You only need to complete the function given below '''\n",
    "#Your task is to complete this Function \\\n",
    "#function should return True/False\n",
    "def isInterleave(A, B, C):\n",
    "    # Code here\n",
    "    if A in C and B in C:\n",
    "        return 1\n",
    "    else:\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "4\n",
      "4 2 5 7\n",
      "4\n",
      "2\n",
      "5\n",
      "5\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "for i in range(int(input())):\n",
    "    n=int(input())\n",
    "    l=list(map(int,input().split()))\n",
    "    for j in range(1,len(l)-1):\n",
    "        max1=max(l[:j+1])\n",
    "        min1=min(l[j:])\n",
    "        if max1==l[j] and min1==l[j]:\n",
    "            print(l[j])\n",
    "            break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for(int i=0;i<=n-k;i++)\n",
    "    {\n",
    "        int a[101]={0},cnt=0;\n",
    "        for(int j=i;j<i+k;j++)\n",
    "        {\n",
    "            if(a[A[j]]==0){a[A[j]]=1;cnt++;}\n",
    "        }\n",
    "        cout<<cnt<<\" \";\n",
    "    }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "73 28\n",
      "8812 3897 2275 8583 6930 2092 4862 8859 7349 4202 7990 5068 6357 1324 8199 8320 5287 1758 4959 1050 3540 2560 3166 3007 2098 9760 5969 1192 1601 6817 6903 6188 6292 5916 7537 9965 8407 5735 4668 7245 4413 5885 2088 3167 3468 7266 8317 8909 5410 2746 2072 3320 8199 4046 9415 3912 8135 8742 7716 9996 7889 4669 5568 9118 7328 8767 9162 8202 6358 3789 4306 5979 2290\n",
      "331 899 356 914 59 104 30 678 534 485 222 6 936 798 504 789 455 695 168 684 822 209 49 348 433 113 288 84 748 927 304 78 825 12 992 236 115 373 265 1000 209 486 6 144 284 861 284 738 907 452 773 729 12 821 428 444 934 715 879 33 993 535 110 170 546 101 405 660 826 21 660 34 507\n",
      "1 . 3897 + 899 = 899\n",
      "2 . 2275 + 356 = 1255\n",
      "3 . 8583 + 914 = 2169\n",
      "7 . 8859 + 678 = 2847\n",
      "8 . 7349 + 534 = 3381\n",
      "12 . 6357 + 936 = 4317\n",
      "14 . 8199 + 504 = 4821\n",
      "16 . 5287 + 455 = 5276\n",
      "18 . 4959 + 168 = 5444\n",
      "23 . 3007 + 348 = 5792\n",
      "26 . 5969 + 288 = 6080\n",
      "28 . 1601 + 748 = 6828\n",
      "29 . 6817 + 927 = 7755\n",
      "30 . 6903 + 304 = 8059\n",
      "34 . 7537 + 992 = 9051\n",
      "35 . 9965 + 236 = 9287\n",
      "36 . 8407 + 115 = 9402\n",
      "37 . 5735 + 373 = 9775\n",
      "39 . 7245 + 1000 = 10775\n",
      "40 . 4413 + 209 = 10984\n",
      "41 . 5885 + 486 = 11470\n",
      "43 . 3167 + 144 = 11614\n",
      "46 . 8317 + 284 = 11898\n",
      "47 . 8909 + 738 = 12636\n",
      "14 . 8199 + 504 = 13140\n",
      "54 . 9415 + 428 = 13568\n",
      "56 . 8135 + 934 = 14502\n",
      "60 . 7889 + 993 = 15495\n",
      "61 . 4669 + 535 = 16030\n",
      "65 . 8767 + 101 = 16131\n",
      "69 . 3789 + 21 = 16152\n",
      "71 . 5979 + 34 = 16186\n",
      "16186\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'\\n1\\n9 15\\n6697 2005 1408 2564 3780 4239 4807 9239 4629\\n167 985 15 402 474 518 478 397 206\\n891    \\n'"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find the fine ---> Microsoft\n",
    "# Difficulty: Basic   Marks: 1\n",
    "for _ in range(int(input())):\n",
    "    n1,n2=input().split()\n",
    "    a1=list(map(int,input().split()))\n",
    "    a2=list(map(int,input().split()))\n",
    "    r=0\n",
    "    for i in a1:\n",
    "        if int(n2)%2==0:\n",
    "            if i%2!=0:\n",
    "                r+=a2[a1.index(i)]\n",
    "                print(a1.index(i),'.',i,'+',a2[a1.index(i)],'=',r)\n",
    "        else:\n",
    "            if i%2==0:\n",
    "                r+=a2[a1.index(i)]\n",
    "    print(r)\n",
    "'''\n",
    "1\n",
    "9 15\n",
    "6697 2005 1408 2564 3780 4239 4807 9239 4629\n",
    "167 985 15 402 474 518 478 397 206\n",
    "891    \n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "a=[1,4,3,8,9,4,7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.index(9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "492"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "16186-15694"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "what are you doing\n",
      "a ae ou oi \n"
     ]
    }
   ],
   "source": [
    "# Remove consonants from a string\n",
    "# Difficulty: Basic   Marks: 1\n",
    "'''\n",
    "Given a string s, remove all consonants and prints the string s that contains vowels only.\n",
    "Input: The first line of input contains integer T denoting the number of test cases. For each test case, we input a string.\n",
    "Output: For each test case, we get a string containing only vowels. If the string doesn't contain any vowels, then print \"No Vowel\"\n",
    "\n",
    "Constraints:\n",
    "\n",
    "1<=T<=100\n",
    "\n",
    "The string should consist of only alphabets.\n",
    "\n",
    "Examples:\n",
    "\n",
    "Input: geEks\n",
    "Output: eE\n",
    "Input: what are you doing\n",
    "Output: a ae ou oi\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    s=input().split(' ')\n",
    "    c=0\n",
    "    for i in range(len(s)):\n",
    "        for j in range(len(s[i])):\n",
    "            if s[i][j] in 'aeiouAEIOU':\n",
    "                print(s[i][j],end='')\n",
    "                c+=1\n",
    "        if c>0:\n",
    "            print(end=' ')\n",
    "    if c==0:\n",
    "        print(\"No Vowel\")\n",
    "    else:\n",
    "        print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "5\n",
      "1 2 3 4 5\n",
      "-1\n"
     ]
    }
   ],
   "source": [
    "# Last duplicate element in a sorted array\n",
    "# Difficulty: Basic   Marks: 1\n",
    "'''\n",
    "Given a sorted array with duplicate elements and we have to find the index of last duplicate element and print index of it and also print the duplicate element.\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. For each test case, the first line contains an integer N denoting the size of array A followed by N-space separated integers denoting the elements of the array.\n",
    "\n",
    "Output:\n",
    "For each test case, the output is two integers denoting the last index of the duplicate element and that duplicate element respectively and if no duplicate element occurs print -1.\n",
    "\n",
    "Constraints:\n",
    "1<=T<=100\n",
    "1<=N<=50\n",
    "1<=A[i]<=50\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "6\n",
    "1 5 5 6 6 7\n",
    "5\n",
    "1 2 3 4 5\n",
    "Output\n",
    "4 6\n",
    "-1\n",
    "\n",
    "Explanation:\n",
    "1.  Last duplicate element is 6 having index 4.\n",
    "2. As no duplicate element exist, hence -1 is printed.\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    c=-1\n",
    "    for i in range(len(a)):\n",
    "        for j in range(i):\n",
    "            if a[i]==a[j]:\n",
    "                c=i\n",
    "                n1=a[i]\n",
    "    if c==-1:\n",
    "        print(-1)\n",
    "    else:\n",
    "        print(c,n1,sep=' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "d\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "# Perfect Square String\n",
    "# Difficulty: Basic   Marks: 1\n",
    "# https://practice.geeksforgeeks.org/problems/perfect-square-string/0/?track=sp-arrays-and-searching&batchId=152\n",
    "'''\n",
    "You are given a string S. Your task is to determine if sum of ASCII values of all character results in a perfect square or not.\n",
    "\n",
    "Input:\n",
    "The first line of the input contains a single integer T, denoting the number of test cases. Then T test cases follow. Each testcase has a string S\n",
    "\n",
    "Output:\n",
    "Print 1 if the resulting sum is a perfect square, else print 0.\n",
    "\n",
    "Constraints:\n",
    "1<=T<=100\n",
    "1<=|S|<=1000\n",
    "\n",
    "Example:\n",
    "\n",
    "Input:\n",
    "4\n",
    "1Qy\n",
    "abcd\n",
    "efgh\n",
    "d\n",
    "\n",
    "Output:\n",
    "0\n",
    "0\n",
    "0\n",
    "1\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    s=input()\n",
    "    r=0\n",
    "    a=[]\n",
    "    for i in s:\n",
    "        r+=ord(i)\n",
    "    for i in range(1,r//2+1):\n",
    "        if r%i==0:\n",
    "            a.append(i)\n",
    "    if len(a)==0:\n",
    "        print(0)\n",
    "    else:\n",
    "        c=0\n",
    "        for i in a:\n",
    "            if i*i==r:\n",
    "                print(1)\n",
    "                c+=1\n",
    "                break\n",
    "        else:\n",
    "            if c==0:\n",
    "                print(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1444\n",
      "14\n"
     ]
    }
   ],
   "source": [
    "for _ in range(int(input())):\n",
    "    n=list(input())\n",
    "    n1=n.copy()\n",
    "    c=0\n",
    "    for i in range(1,len(n)):\n",
    "        if n[i]==n[i-1]:\n",
    "            #del n1[i]\n",
    "            n1.remove(n1[i-c])\n",
    "            c+=1\n",
    "    print(*(n1),sep='')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1122455\n",
      "1245\n"
     ]
    }
   ],
   "source": [
    "# Remove repeated digits in a given number\n",
    "# Difficulty: Basic   Marks: 1\n",
    "'''\n",
    "Given an integer N, remove consecutive repeated digits from it.\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains the integer N.\n",
    "\n",
    "Output:\n",
    "Print the number after removing consecutive digits. Print the answer for each test case in a new line.\n",
    "\n",
    "\n",
    "Constraints:\n",
    "1<= T <=100\n",
    "1<= N <=1018\n",
    "\n",
    "\n",
    "Example:\n",
    "\n",
    "Input:\n",
    "2\n",
    "12224\n",
    "87635887\n",
    "Output:\n",
    "124\n",
    "8763587\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    n=list(input())\n",
    "    n1=n.copy()\n",
    "    c=0\n",
    "    for i in range(len(n)):\n",
    "        for j in range(i):\n",
    "            if n[j]==n[i]:\n",
    "                del n1[i-c]\n",
    "                #n1.remove(n[i])\n",
    "                c+=1\n",
    "                break\n",
    "    print(*(n1),sep='')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "31\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "# Super Primes\n",
    "# Difficulty: Medium   Marks: 4\n",
    "def isPrime(x):\n",
    "    for j in range(3,x//2+1,2):\n",
    "        if x%j==0:\n",
    "            return False\n",
    "    else:\n",
    "        return True\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=[2]\n",
    "    a1=[]\n",
    "    for i in range(3,n+1,2):\n",
    "        if isPrime(i):\n",
    "            a.append(i)\n",
    "            for k in range(len(a)):\n",
    "                for k1 in range(k+1,len(a)):\n",
    "                    if (a[k]+a[k1])==a[-1] and (a[k]+a[k1])<=a[-1]:\n",
    "                        a1.append(a[-1])\n",
    "                        break\n",
    "    print(len(a1))\n",
    "#     print(a[:],sep=' ')\n",
    "#     print(a1[:],sep=' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "7\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# Super Primes\n",
    "# Difficulty: Medium   Marks: 4\n",
    "def isPrime(n) : \n",
    "\tif (n <= 1) : \n",
    "\t\treturn False\n",
    "\tif (n <= 3) : \n",
    "\t\treturn True\n",
    "\tif (n % 2 == 0 or n % 3 == 0) : \n",
    "\t\treturn False\n",
    "\ti = 5\n",
    "\twhile(i * i <= n) : \n",
    "\t\tif (n % i == 0 or n % (i + 2) == 0) : \n",
    "\t\t\treturn False\n",
    "\t\ti = i + 6\n",
    "\n",
    "\treturn True\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=[2]\n",
    "    a1=[]\n",
    "    for i in range(3,n+1,2):\n",
    "        if isPrime(i):\n",
    "            a.append(i)\n",
    "            for k in range(len(a)):\n",
    "                for k1 in range(k+1,len(a)):\n",
    "                    if (a[k]+a[k1])==a[-1] and (a[k]+a[k1])<=a[-1]:\n",
    "                        a1.append(a[-1])\n",
    "                        break\n",
    "    print(len(a1))\n",
    "#     print(a[:],sep=' ')\n",
    "#     print(a1[:],sep=' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7, 13, 19, 31]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "98\n",
      "NO\n"
     ]
    }
   ],
   "source": [
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    if n==1:\n",
    "        print('YES')\n",
    "    else:\n",
    "        l=1\n",
    "        for i in range(2,n//2+1):\n",
    "            l=l*2\n",
    "            if l==n:\n",
    "                print('YES')\n",
    "                break\n",
    "        else:\n",
    "            print('NO')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(11).split('0b')[1].count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "print(int('101',base=2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "10 4\n",
      "5040\n"
     ]
    }
   ],
   "source": [
    "def fact(n):\n",
    "    f=1\n",
    "    for i in range(1,n+1):\n",
    "        f=f*i\n",
    "    else:\n",
    "        return f\n",
    "for _ in range(int(input())):\n",
    "    n,r=input().split()\n",
    "    print(fact(int(n))//fact(int(n)-int(r)))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "123\n",
      "321\n"
     ]
    }
   ],
   "source": [
    "for _ in range(int(input())):\n",
    "    l=list(input())\n",
    "    l[::1]=l[-1::-1]\n",
    "    sum=0\n",
    "    for i in range(len(l)):\n",
    "        sum+=int(l[i])*(10**(len(l)-i-1))\n",
    "    print(sum)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "36 9\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "def div(n):\n",
    "    for i in range(2,n//2+1):\n",
    "        if n%i==0:\n",
    "            yield i\n",
    "    else:\n",
    "        yield n\n",
    "for _ in range(int(input())):\n",
    "    n1,n2=map(int,input().split())\n",
    "    a1=list(div(n1))\n",
    "    a2=list(div(n2))\n",
    "    c=1\n",
    "    for i in a1:\n",
    "        for j in a2:\n",
    "            if i==j:\n",
    "                c=i\n",
    "                break\n",
    "    print(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "3\n",
      "YES\n"
     ]
    }
   ],
   "source": [
    "#code\n",
    "def isPrime(x):\n",
    "    if x == 1:\n",
    "        return False\n",
    "    for j in range(3,x//2+1,2):\n",
    "        if x%j==0:\n",
    "            return False\n",
    "    else:\n",
    "        return True\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    if n%2==0 and n!=2:\n",
    "        print('NO')\n",
    "    else:\n",
    "        if isPrime(n):\n",
    "            print('YES')\n",
    "        else:\n",
    "            print('NO')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "35\n",
      "NO\n"
     ]
    }
   ],
   "source": [
    "#code\n",
    "def isPrime(x):\n",
    "    if x <= 1:\n",
    "        return False\n",
    "    if x<=3:\n",
    "        return True\n",
    "    if x%2==0 or x%3==0:\n",
    "        return False\n",
    "    for j in range(5,x//2+1,2):\n",
    "        if x%j==0:\n",
    "            return False\n",
    "    else:\n",
    "        return True\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    if isPrime(n):\n",
    "        print('Yes')\n",
    "    else:\n",
    "        print('No')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "3\n",
      "Yes\n"
     ]
    }
   ],
   "source": [
    "#code\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    if n>1:\n",
    "        for i in range(2,n//2+1):\n",
    "            if n%i==0:\n",
    "                print('No')\n",
    "                break\n",
    "        else:\n",
    "            print('Yes')\n",
    "    else:\n",
    "        print('No')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      " false\n"
     ]
    }
   ],
   "source": [
    "def isPrime(n) : \n",
    "\tif (n <= 1) : \n",
    "\t\treturn False\n",
    "\tif (n <= 3) : \n",
    "\t\treturn True\n",
    "\tif (n % 2 == 0 or n % 3 == 0) : \n",
    "\t\treturn False\n",
    "\ti = 5\n",
    "\twhile(i * i <= n) : \n",
    "\t\tif (n % i == 0 or n % (i + 2) == 0) : \n",
    "\t\t\treturn False\n",
    "\t\ti = i + 6\n",
    "\n",
    "\treturn True\n",
    "for _ in range(int(input())):\n",
    "    if (isPrime(int(input()))) : \n",
    "        print(\"Yes\") \n",
    "    else : \n",
    "        print(\"No\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "36 9\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "def div(n):\n",
    "    for i in range(2,n//2+1):\n",
    "        if n%i==0:\n",
    "            yield i\n",
    "    else:\n",
    "        yield n\n",
    "for _ in range(int(input())):\n",
    "    n1,n2=map(int,input().split())\n",
    "    a1=list(div(n1))\n",
    "    a2=list(div(n2))\n",
    "    ac1=a1.copy()\n",
    "    ac2=a2.copy()\n",
    "    c=1\n",
    "    for i in a1:\n",
    "        for j in a2:\n",
    "            if i==j:\n",
    "                c=i\n",
    "                ac1.remove(i)\n",
    "                ac2.remove(i)\n",
    "                break\n",
    "    print(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "101\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n",
      "25\n"
     ]
    }
   ],
   "source": [
    "def isPrime(n) : \n",
    "    if (n <= 1) : \n",
    "        return False\n",
    "    if (n <= 3) : \n",
    "        return True\n",
    "    if (n % 2 == 0 or n % 3 == 0) : \n",
    "        return False\n",
    "    i = 5\n",
    "    while(i * i <= n) :\n",
    "        print(i*i)\n",
    "        if (n % i == 0 or n % (i + 2) == 0):\n",
    "            return False\n",
    "        i = i + 6\n",
    "    return True\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    sum=0\n",
    "    for i in range(n+1):\n",
    "        isPrime(i)\n",
    "#     if n<=1:\n",
    "#         print(sum)\n",
    "#         continue\n",
    "#     if n==2:\n",
    "#         print(sum)\n",
    "#         continue\n",
    "#     if n==3:\n",
    "#         print(5)\n",
    "#         continue\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "10\n",
      "12\n"
     ]
    }
   ],
   "source": [
    "#code\n",
    "def ugly(n):\n",
    "    if n<7:\n",
    "        return True\n",
    "    else:\n",
    "        n1=n\n",
    "        while n1!=1:\n",
    "            if n1%2==0:\n",
    "                n1/=2\n",
    "            if n1%3==0:\n",
    "                n1/=3\n",
    "            if n1%5==0:\n",
    "                n1/=5\n",
    "            if n1>n//2:\n",
    "                break\n",
    "        if n1==1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=[]\n",
    "    i=0\n",
    "    c=0\n",
    "    while True:\n",
    "        i+=1\n",
    "        if ugly(i)==True:\n",
    "            a.append(i)\n",
    "            c+=1\n",
    "        if c==n:\n",
    "            break\n",
    "    print(a[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "10\n",
      "12\n"
     ]
    }
   ],
   "source": [
    "def divide(a,b):\n",
    "    while a%b==0:\n",
    "        a/=b\n",
    "    return a\n",
    "def isUgly(n):\n",
    "    n=divide(n,2)\n",
    "    n=divide(n,3)\n",
    "    n=divide(n,5)\n",
    "    if n==1:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    count=0\n",
    "    i=0\n",
    "    while count!=n:\n",
    "        i+=1\n",
    "        if isUgly(i):\n",
    "            count+=1\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 0]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[0]*3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2 8\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "#code\n",
    "def isDivide(a,b):\n",
    "    while b%a==0:\n",
    "        b/=a\n",
    "    if b==1:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "for _ in range(int(input())):\n",
    "    a,b=input().split()\n",
    "    f=1\n",
    "    print(isDivide(int(a),int(b)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2 8\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "# Check if a number is power of another number ---> SAP Labs, Zoho\n",
    "# Difficulty: Basic   Marks: 1\n",
    "'''\n",
    "Given two positive numbers x and y, check if y is a power of x or not.\n",
    "\n",
    "Input:\n",
    "First line contains an integer, the number of test cases 'T'. Each test case should contain two positive numbers x and y.\n",
    "\n",
    "Output:\n",
    "Print 1 if y is a power of x, else print 0.\n",
    "\n",
    "Constraints: \n",
    "1 <= T <= 30\n",
    "1 <= x <= 103\n",
    "1 <= y <= 108\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "2 8\n",
    "1 3\n",
    "Output:\n",
    "1\n",
    "0\n",
    "\n",
    "Explanation: 8 is a power of 2, but 3 is not a power of 1.\n",
    "'''\n",
    "import math\n",
    "for _ in range(int(input())):\n",
    "    a,b=input().split()\n",
    "    try:\n",
    "        res=math.log(int(b))/math.log(int(a))\n",
    "        if (int(res)-res)==0:\n",
    "            print(1)\n",
    "        else:\n",
    "            print(0)\n",
    "    except Exception as e:\n",
    "        print(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "12 21\n",
      "-244\n"
     ]
    }
   ],
   "source": [
    "#code\n",
    "for _ in range(int(input())):\n",
    "    h,m=input().split()\n",
    "    a=(5/12)*(int(m)/5)\n",
    "    if a==5:\n",
    "        a=0\n",
    "    print(int((int(m)-(a+int(h)*5))*6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "a=(5/12)*(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a==5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17.5"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "15+2.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12.5"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "30-17.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "75.0"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "12.5*6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "60-45"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "117"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "360-243"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "12 21.1274\n",
      "116\n"
     ]
    }
   ],
   "source": [
    "# Angle between hour and minute hand ---> Amazon, Infineria, Paytm, Salesforce\n",
    "# Difficulty: Basic   Marks: 1\n",
    "'''\n",
    "Calculate the angle between hour hand and minute hand.\n",
    "\n",
    "There can be two angles between hands, we need to print minimum of two. Also, we need to print floor of final result angle. For example, if the final angle is 10.61, we need to print 10.\n",
    "\n",
    " \n",
    "\n",
    "Input:\n",
    "\n",
    "The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of one line conatining two space separated numbers h and m where h is hour and m is minute.\n",
    "\n",
    "Output:\n",
    "Coresponding to each test case, print the angle b/w hour and min hand in a separate line.\n",
    "\n",
    "Constraints:\n",
    "\n",
    "1 ≤ T ≤ 100\n",
    "1 ≤ h ≤ 12\n",
    "1 ≤ m ≤ 60\n",
    "\n",
    "Example:\n",
    "\n",
    "Input\n",
    "2\n",
    "9 60\n",
    "3 30\n",
    "\n",
    "Output\n",
    "90\n",
    "75\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    h,m=input().split()\n",
    "    a=(5/12)*(float(m)/5)\n",
    "    if int(a)==5:\n",
    "        a=0\n",
    "    b=abs((float(m)-(a+int(h)*5))*6)\n",
    "    if b>(360-b):\n",
    "        b=360-b\n",
    "    print(int(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "16 02 1996\n",
      "Friday\n"
     ]
    }
   ],
   "source": [
    "# Day of the week ---> Microsoft, Mortan Stantey, Samsung\n",
    "# Difficulty: Easy   Marks: 2\n",
    "'''\n",
    "Write a program that calculates the day of the week for any particular date in the past or future.\n",
    "\n",
    "Input:\n",
    "\n",
    "The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consist of one line. The first line of each test case consists of an integer d,m and y, d is day, m is month and y is the year.\n",
    "\n",
    "Output:\n",
    "\n",
    "Print day of given date.\n",
    "\n",
    "Constraints:\n",
    "\n",
    "1 ≤ T ≤ 100\n",
    "1990 ≤ Y ≤ 2100\n",
    "\n",
    "Example:\n",
    "\n",
    "Input:\n",
    "\n",
    "2\n",
    "\n",
    "28 12 1995\n",
    "\n",
    "30 8 2010\n",
    "\n",
    "Output\n",
    "\n",
    "Thursday\n",
    "\n",
    "Monday\n",
    "'''\n",
    "import calendar as cd\n",
    "for _ in range(int(input())):\n",
    "    d,m,y=map(int,input().split())\n",
    "    days=[\"Monday\",\"Tuesday\",\"Wednesday\",\"Thursday\",\"Friday\",\"Saturday\",\"Sunday\"]\n",
    "    f=cd.weekday(y,m,d)\n",
    "    print(days[f])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "78 88 89 99 45 55 56 66\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "# Check if given four points form a square ---> Amazon\n",
    "# Difficulty: Basic   Marks: 1\n",
    "'''\n",
    "Given coordinates of four points in a plane, find if the four points form a square or not.\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains 4 space separated integer points a , b , c , d\n",
    "\n",
    "Output:\n",
    "For each test case print 1 if the four points form a square else print 0.\n",
    "Remember to output the answer of each test case in a new line.\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 200\n",
    "1 <= a,b,c,d <= 100\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "20 20 20 10 10 20 10 10\n",
    "10 10 10 10 20 10 20 30\n",
    "Output:\n",
    "1\n",
    "0\n",
    "'''\n",
    "from collections import Counter\n",
    "def dist(x1,y1,x2,y2):\n",
    "    return (abs(x2-x1)**2+abs(y2-y1)**2)\n",
    "for _ in range(int(input())):\n",
    "    m=input()\n",
    "    try:\n",
    "        a,b,c,d,e,f,g,h=(map(int,m.split()))\n",
    "    except:\n",
    "        a,c,e,g=(map(int,m.split()))\n",
    "        b,d,f,h=[0]*4\n",
    "    l=[a,b,c,d,e,f,g,h]\n",
    "    if dist(a,b,e,f)==dist(c,d,g,h) and len(Counter(l).keys())==2:\n",
    "        print(1)\n",
    "    else:\n",
    "        print(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=22\n",
    "str(a).count('2')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "4 5\n",
      "2 6 3 12 56 8\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "#code\n",
    "for _ in range(int(input())):\n",
    "    n,p=input().split()\n",
    "    a=list(map(int,input().split()))\n",
    "    a.sort()\n",
    "    print(*(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "7 50\n",
      "1 12 5 111 200 1000 10\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "#code\n",
    "for _ in range(int(input())):\n",
    "    n,p=input().split()\n",
    "    a=list(map(int,input().split()))\n",
    "    a.sort()\n",
    "    i=0\n",
    "    p=int(p)\n",
    "    while True:\n",
    "        if p>=a[i]:\n",
    "            p-=a[i]\n",
    "            i+=1\n",
    "        else:\n",
    "            break\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "8\n",
      "3 1 0 2 5 4 1 2\n",
      "4\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    frame_size=int(input())\n",
    "    frame=[None]*frame_size\n",
    "    c=0\n",
    "    fault=0\n",
    "    for i in range(len(a)):\n",
    "        if a[i] not in frame:\n",
    "            frame[c]=a[i]\n",
    "            fault+=1\n",
    "        c+=1\n",
    "        if c>3:\n",
    "            c%=frame_size\n",
    "    print(fault)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "8\n",
      "3 1 0 2 5 4 1 2\n",
      "4\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "# Page Faults in LRU\n",
    "# Difficulty: Medium   Marks: 4\n",
    "'''\n",
    "In operating systems that use paging for memory management, page replacement algorithm are needed to decide which page needs to be replaced when the new page comes in. Whenever a new page is referred and is not present in memory, the page fault occurs and Operating System replaces one of the existing pages with a newly needed page. Given a sequence of pages and memory capacity, your task is to find the number of page faults using Least Recently Used (LRU) Algorithm.\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. Each test case contains n number of pages and next line contains space seaprated sequence of pages. The following line consist of the capacity of the memory.\n",
    "Note: Pages are referred in the order left to right from the array (i.e index 0 page is referred first then index 1 and so on). Memory is empty at the start.\n",
    "\n",
    "Output:\n",
    "Output the number of page faults.\n",
    "\n",
    "Constraints:\n",
    "1<=T<=100\n",
    "1<=n<=1000\n",
    "4<=capacity<=100\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "9\n",
    "5 0 1 3 2 4 1 0 5\n",
    "4\n",
    "8\n",
    "3 1 0 2 5 4 1 2\n",
    "4\n",
    "\n",
    "Output:\n",
    "8\n",
    "7\n",
    "\n",
    "Explanation:\n",
    "Testcase 1:\n",
    "memory allocated with 4 pages 5, 0, 1, 3: page fault = 4\n",
    "page number 2 is required, replaces LRU 5: page fault = 4+1 = 5\n",
    "page number 4 is required, replaces LRU 0: page fault = 5 + 1 = 6\n",
    "page number 1 is required which is already present: page fault = 6 + 0 = 6\n",
    "page number 0 is required which replaces LRU 1: page fault = 6 + 1 = 7\n",
    "page number 5 is required which replaces LRU 3: page fault = 7 + 1  =8.\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    frame_size=int(input())\n",
    "    frame=[]\n",
    "    fault=0\n",
    "    for i in range(len(a)):\n",
    "        if fault<frame_size:\n",
    "            if a[i] not in frame:\n",
    "                frame.append(a[i])\n",
    "                fault+=1\n",
    "            else:\n",
    "                frame.remove(a[i])\n",
    "                frame.append(a[i])\n",
    "        else:\n",
    "            if a[i] not in frame:\n",
    "                frame.pop(0)\n",
    "                frame.append(a[i])\n",
    "                fault+=1\n",
    "            else:\n",
    "                frame.remove(a[i])\n",
    "                frame.append(a[i])\n",
    "            \n",
    "    print(fault)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "35 0\n",
      "-1\n"
     ]
    }
   ],
   "source": [
    "# Largest number possible\n",
    "# Difficulty: Easy   Marks: 2\n",
    "'''\n",
    "Given two numbers 'N' and 'S' , find the largest number that can be formed with 'N' digits and whose sum of digits should be equals to 'S'.\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains two space separated integers N and S, where N is the number of digits and S is the sum.\n",
    "\n",
    "Output:\n",
    "Print the largest number that is possible.If their is no such number, then print -1 \n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 30\n",
    "1 <= N <= 50\n",
    "0 <= S <= 500\n",
    "\n",
    "Example: \n",
    "Input:\n",
    "2\n",
    "2 9\n",
    "3 20\n",
    "Output: \n",
    "90\n",
    "992 \n",
    "\n",
    "Expected Time Complexity: O(n)\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    a,b=input().split()\n",
    "    b=int(b)\n",
    "    max_sum=9*int(a)\n",
    "    digit=0\n",
    "    if b>max_sum or b==0:\n",
    "        print(-1)\n",
    "    else:\n",
    "        for i in range(int(a)):\n",
    "            for j in range(9,-1,-1):\n",
    "                if b-j>=0:\n",
    "                    b=b-j\n",
    "                    digit+=j*(10**(int(a)-i-1))\n",
    "                    break\n",
    "        print(digit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "3\n",
      "aba\n",
      "Yes\n"
     ]
    }
   ],
   "source": [
    "# Palindrome String ---> Amazon, Cisco, D-E-Shaw, Facebook, FacSet, Morgan Stanley, Paytm, Zoho\n",
    "# Difficulty: School   Marks: 0\n",
    "'''\n",
    "Given a string S, check if it is palindrome or not.\n",
    "\n",
    "Input:\n",
    "The first line contains 'T' denoting the number of test cases. T testcases follow. Each testcase contains two lines of input. The first line contains the length of the string and the second line contains the string S.\n",
    "\n",
    "Output:\n",
    "For each testcase, in a new line, print \"Yes\" if it is a palindrome else \"No\". (Without the double quotes)\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 30\n",
    "1 <= N <= 100\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "1\n",
    "4\n",
    "abba\n",
    "Output:\n",
    "Yes\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    s=input()\n",
    "    if n%2==0:\n",
    "        if s[:n//2]==s[-1:n//2-1:-1]:\n",
    "            print('Yes')\n",
    "        else:\n",
    "            print('No')\n",
    "    else:\n",
    "        if s[:n//2]==s[-1:n//2:-1]:\n",
    "            print('Yes')\n",
    "        else:\n",
    "            print('No')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "12\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# Find first set bit ---> Amazon\n",
    "# Difficulty: Basic   Marks: 1\n",
    "'''\n",
    "Given an integer an N. The task is to print the position of first set bit found from right side in the binary representation of the number.\n",
    "\n",
    "Input:\n",
    "The first line of the input contains an integer T, denoting the number of test cases. Then T test cases follow. The only line of the each test case contains an integer N.\n",
    "\n",
    "Output:\n",
    "For each test case print in a single line an integer denoting the position of the first set bit found form right side of the binary representation of the number. If there is no set bit print \"0\".\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 200\n",
    "0 <= N <= 106\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "18\n",
    "12\n",
    "\n",
    "Output:\n",
    "2\n",
    "3\n",
    "\n",
    "Explanation:\n",
    "Testcase 1: Binary representation of the 18 is 010010, the first set bit from the right side is at position 2.\n",
    "'''\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    r=bin(n)[::-1].find('1')+1\n",
    "    print(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "a=[1,2,3,4,5,6,7,8,9]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "b=[1,2,3,4,5,7,8,9]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "print(list(set(a)^set(b))[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Shortest path from 1 to n ---> Accolite, Cisco, Morgan Stanley, Samsung, Synopsys\n",
    "# Difficulty: Basic   Marks: 1\n",
    "'''\n",
    "Consider a directed graph whose vertices are numbered from 1 to n. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The task is to find the minimum number of edges in a path in G from vertex 1 to vertex n.\n",
    "\n",
    "Input: \n",
    "The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.\n",
    "\n",
    "Each test case contains a value of n. \n",
    "\n",
    "Output: \n",
    "Print the number of edges in the shortest path from 1 to n.\n",
    "\n",
    "Constraints:\n",
    "1<=T<=30\n",
    "1<=n <=1000\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "9\n",
    "4\n",
    "\n",
    "Output:\n",
    "2\n",
    "2\n",
    "'''\n",
    "def do(n):\n",
    "    if n<2:\n",
    "        return 0\n",
    "    if n==2:\n",
    "        return 1 \n",
    "    return ((n%3)+1+do(n//3))\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    print(int(do(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "5\n",
      "3 4 5 1 2\n",
      "5 4\n"
     ]
    }
   ],
   "source": [
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    print(max(a),end=' ')\n",
    "    b=a.copy()\n",
    "    _max=max(a)\n",
    "    print(_max)\n",
    "    if a.index(_max)==0:\n",
    "        print(2)\n",
    "    elif a.index(_max)==(len(a)-1):\n",
    "        print(1)\n",
    "    elif "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "a=[3,4,5,1,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "b=a.copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b.index(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "b.sort(reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "a.sort(reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 4, 3, 2, 1]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 4, 3, 2, 1]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a==b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}