void split(node *root)
{
	node *one=createnode(-1);
	node *two=createnode(-1);
	node *first=one;
	node *second=two;
	node *temp=root;
	node *temp1=root->next;
	while(temp1!=NULL)
	{
		one->next=temp;
		two->next=temp1;
		one=temp;
		two=temp1;
		temp=temp->next->next;
		temp1=temp1->next->next;
		temp->next=NULL;
		temp1->next=NULL;
	}
	print(first);
	print(second);



}

/* Add a new node to the tree */
Node *addnode(Name *pName, Node* pNode)
{
  if(!pNode)                               /* If there's no node              */
    return createnode(pName);              /* ...create one and return it     */

  if(compare(pName, pNode->pName) == 0)
  {                                        /* Name equals current node        */
    ++pNode->count;                        /* ...so increment count and       */
    return pNode;                          /* ...return the same node         */
  }

  if(compare(pName, pNode->pName) < 0)     /* If less than current node name  */
  {
    if(!pNode->pLeft)                      /* and there's no left node        */
    {
      pNode->pLeft = createnode(pName);    /* create a new left node and      */
      return pNode->pLeft;                 /* return it.                      */
    }
    else                                   /* If there is a left node...      */
      return addnode(pName, pNode->pLeft); /* add value via the left node     */
  }
  else                                     /* value is greater than current   */
  {
    if(!pNode->pRight)                     /* so the same process with        */
    {                                      /* the right node.                 */
      pNode->pRight = createnode(pName);
      return pNode-> pRight;
    }
    else
      return addnode(pName, pNode->pRight);
  }
}

int main(){
	struct node *head=NULL,*temp;
	int i,j,n;
	char c='y';
	do{
		scanf("%d",&n);
		if(!head){
			head=createnode(n);
			temp=head;
		}
		else{
			while(temp->next){
				temp=temp->next;
			}
			temp->next=createnode(n);
		}
		printf("Press y to continue: ");
		fflush(stdin);
		scanf("%c",&c);
		
	}while(c=='y'|| c=='Y');
	
	printll(head);
	mergesort(&head);
	printf("Sorted ");
	printll(head);
	return 0;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int n,data,pos;
	printf("enter no of nodes in linked list1\n");
	scanf("%d",&n);
	printf("enter data part of linked list1\n");
	scanf("%d",&data);
	root=createnode(data);
	node *temp=root;
	node *temp1;
	for(int i=1;i<n;i++)
	{
		printf("enter data part of linked list\n");
		scanf("%d",&data);
		temp1=createnode(data);
		temp->next=temp1;
		temp=temp1;
	}
	print(root);
	printf("enter the position\n");
	scanf("%d",&pos);
	node *res=rotate(root,pos,n);
	print(res);
	return 0;
}

/* Add a new node to the tree */
struct Node *addnode(long value, struct Node* pNode)
{
  if(pNode == NULL)                        /* If there's no node              */
    return createnode(value);              /* ...create one and return it     */

  if(value ==pNode->item)
  {                                        /* Value equals current node       */
    ++pNode->count;                        /* ...so increment count and       */
    return pNode;                          /* ...return the same node         */
  }

  if(value < pNode->item)                  /* If less than current node value */
  {
    if(pNode->pLeft == NULL)               /* and there's no left node        */
    {
      pNode->pLeft = createnode(value);    /* create a new left node and      */
      return pNode->pLeft;                 /* return it.                      */
    }
    else                                   /* If there is a left node...      */
      return addnode(value, pNode->pLeft); /* add value via the left node     */
  }
  else                                     /* value is greater than current   */
  {
    if(pNode->pRight == NULL)              /* so the same process with        */
    {                                      /* the right node.                 */
      pNode-> pRight = createnode(value);
      return pNode-> pRight;
    }
    else
      return addnode(value, pNode-> pRight);
  }
}

int main(){
	int t,m,n,i,j,*a,count,x=0;
	struct node *l,*head,*last;
	scanf("%d",&t);
	while(t--){
		count=0;
		x=0;
		scanf("%d%d",&n,&m);
		a=(int*)malloc(m*sizeof(int));
		for(i=0;i<m;i++){
			scanf("%d",&a[i]);
			if(a[i]==1){
				x++;
			}
		}
		if(x==m){
			count=floor(x/2);
		}
		else{
			quicksort(a,0,m-1);
			
			
			
			head=createnode(a[0]);
			l=head;
			//last=NULL;
			for(i=1;i<m;i++){
				struct node *temp;
				temp=createnode(a[i]);
				temp->l=l;
				l->r=temp;
				l=l->r;
			}
			last=l;
			//printll(head);
			struct node *t=head;
			while(t!=last){
				//printll(t);
				if(t->val==0){
					t=t->r;
				}
				else{
					(t->val)--;
					int p = last->val+(last->l->val);
				//	printf("\nt: %d last %d last->left: %d p: %d",t->val,last->val,last->l->val,p);
					last=last->l;
					last->r=NULL;
					last->val=p;
					count++;
				}
			//	printll(t);
		}
		}
		printf("%d\n",count);
	}
}

int main()
{
    node *root=createnode(1);
    for(int i=2;i<100;i++)
    {
            system("cls");
            insertleaf(createnode(i),root);
    }
    return 0;
}

void main()
{
	struct node* head, *temp, *prev;
	head = NULL;
	head = createnode(head, 2);
	head = createnode(head, 3);
	head = createnode(head, 90);
	head = createnode(head, 1);
	head = createnode(head, 4);
	head = createnode(head, 5);
	head = createnode(head, 6);
	head = createnode(head, 8);
	head = createnode(head, 0);

	temp = head;
	while (temp != NULL)
	{
		printf("\ntemp_num:%d\ttemp_bit:%d", temp->num, temp->bit);
		temp = temp->next;
	}
	temp = head->next;
	loop_pos(head);

	_getch();

}

struct ip4trie_node *
ip4trie_addnode(struct ip4trie *trie, ip4addr_t prefix, unsigned bits,
                struct mempool *mp) {
  struct ip4trie_node *node, **last;

  for(last = &trie->ip4t_root;
      (node = *last) != NULL;
      last = bitset(prefix, node->ip4t_bits) ?
         &node->ip4t_right : &node->ip4t_left) {

    if (node->ip4t_bits > bits ||
       !prefixmatch(node->ip4t_prefix, prefix, node->ip4t_bits)) {
      /* new node should be inserted before the given node */
      struct ip4trie_node *newnode;

      /* Find number of common (equal) bits */
      ip4addr_t diff = (prefix ^ node->ip4t_prefix) & ip4mask(bits);
      unsigned cbits;
      if (!diff) /* no difference, all bits are the same */
        cbits = bits;
      else {
        cbits = 0;
        while((diff & ip4mask(cbits+1)) == 0)
          ++cbits;
      }
      ++trie->ip4t_nnodes;
      if (!(newnode = createnode(prefix & ip4mask(cbits), cbits, mp)))
        return NULL;
      linknode(newnode, node);
      *last = newnode;
      if (cbits == bits)
        return newnode;
      /* so we just inserted a glue node, now insert real one */
      ++trie->ip4t_nnodes;
      if (!(node = createnode(prefix, bits, mp)))
          return NULL;
      linknode(newnode, node);
      return node;
    }

    /* node's prefix matches */
    if (node->ip4t_bits == bits)/* if number of bits are the same too, */
      return node;		/* ..we're found exactly the same prefix */

  }

  /* no more nodes, create simple new node */
  ++trie->ip4t_nnodes;
  if (!(node = createnode(prefix, bits, mp)))
    return NULL;
  *last = node;
  return node;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{   int count=0,index=0;
    FILE* fp = fopen(dictionary, "r");
    if (fp == NULL)
    {
        return false;
    }
    char dis[45]={ };
    node* temp=root;
    int c=fgetc(fp);
     root=createnode();
        

    while(c!=EOF)
    {   temp=root;
        while(c!='\n')
        {
            dis[count++]=c;
            c=fgetc(fp);
        }
        for(int i=0;i<count;i++)
        {   
            if((index=chartoascii(dis[i]))!=-1)
            {
               
                
                    if(temp->children[index]==NULL)
                    {
                        temp->children[index]=createnode();
                        temp=temp->children[index];
                        
                    }
                    else
                    {
                        temp=temp->children[index];
                    }
                
                
            }
            
            
            
        }
        temp->is_word=true;
        track++;
    
        c=fgetc(fp);
        count=0;
    }
    
    fclose(fp);
    return true;
}

void add(FileInfo data, List * list){
  Node * current = NULL;
  if(list->head == NULL){
    list->head = createnode(data);
  }
  else {
    current = list->head; 
    while (current->next!=NULL){
      current = current->next;
    }
    current->next = createnode(data);
  }
}

int main()
{
	 instruction();
     extern int i;
     	//setting up trie to store keywords......
		 initialize(&trie);
	
     int j;	
     struct name *temp;
     name=createnode();
     name_next=name;
     for(j=1;j<=i;j++)
	 {
	 	get_file(name_next->file);
	 	name_next->frequency=1;
	 	name_next->id=j;
	 	
	 if(j<i)
	 	 {
		    temp=createnode();
	 	    name_next->node=temp;
	 	    name_next=temp;
	     }
	 }
	 name_next->node=NULL;
	 name_next=name;
	 for(j=1;j<=i;j++)
	 {
	 	file_read(name_next->file,name_next->id);
	 	printf("yes it one");
	 	system("cls");
	 	printf("loading....");
		name_next=name_next->node;
	 	
	 }
	 system("cls");
	 int pal=1;
	 char take[100];
	 while(take[0]!='0')
	 { printf("\nEnter word to search:");
	 scanf("%s",take);
	 pal=search(&trie, take);
	 if(pal==0)
	 {
	 	printf("not exist");
	 }
	 
	
     }
	 
}

void main()
{
    struct node* head, *temp;
    head = NULL;
    head = createnode(head, 0);
    head = createnode(head, 1);
    head = createnode(head, 2);
    head = createnode(head, 3);
    head = createnode(head, 4);
    head = createnode(head, 5);
    head = createnode(head, 6);
    head = createnode(head, 7);
    //head = createnode(head, 8);
    temp = head;
    printf("\nlist:\n");
    while (temp != NULL)
    {
        printf("%d\t", temp->num);
        temp = temp->next;
    }
    median(head);

    _getch();

}

void insertlast(node** head)
{
	if((*head)==NULL)
		(*head)=createnode(insertdata());
	else
	{

		node* temp=(*head);
		while(temp->next!=NULL)
			temp=temp->next;

		temp->next=createnode(insertdata());
	}

}

void insertbeg(node** head)
{
	node* temp=createnode(insertdata());
	temp->next=(*head);
	(*head)=temp;

}

int _tmain(int argc, _TCHAR* argv[])
{
	int n,ch;
	printf("enter no of nodes in linked list\n");
	scanf("%d",&n);
	root->data=1;
	root->next=NULL;
	node *temp=root;
	node *temp1;
	for(int i=2;i<=n;i++)
	{
		temp1=createnode(i);
		temp->next=temp1;
		temp=temp1;
	}
	print(root);
	printf("\n\nenter your choice of alternating deletion\n1.even places\n2.odd places\nenter your choice\n");
	scanf("%d",&ch);
	switch(ch)
	{
	case 1:temp1=even(root);
		    print(temp1);
		    break;
	case 2:temp1=odd(root);
		    print(temp1);
		    break;
	default:
		    printf("enter correct choice\n");
			break;
	}

	return 0;
}

void insert(Skiplist *skiplist, DataType data, int (*compare)(DataType v1, DataType v2))
{
    Node *next = NULL;
    Node *cur = skiplist->head;

    Node *updates[MAX_LEVEL] = {NULL};
    for(int i = skiplist->level - 1; i >= 0; --i)
    {
        while((next = cur->nexts[i]) && compare(data, next->data) > 0)
        {
            cur = next;
        }
        updates[i] = cur;
    }

    int level = randomlevel(MAX_LEVEL);
    if(level > skiplist->level)
    {
        for(int i = skiplist->level; i < level; ++i)
        {
            updates[i] = skiplist->head;
        }
        skiplist->level = level;
    }

    Node *node = createnode(level, data);
    for(int i = level - 1; i >= 0; --i)
    {
        node->nexts[i] = updates[i]->nexts[i];
        updates[i]->nexts[i] = node;
    }
}

struct bsnode* insert(struct bsnode* root,char data[])
{
//printf("insert");
if(root==NULL)
{
root= createnode(data);
//printf("\n",root->data);
 }
else if(toint(root->data) >=toint(data))
{
root->left=insert(root->left,data);
// printf("\nleft%d",root->data);
printf("\n");

}
else
{
root->right=insert(root->right,data);
//printf("\nRIGHT");
//printf("\n\t");
}

//printf("inseted data %s",data);
 return root;
}

void insertn(node **head,int n)
{

	if((*head)==NULL)
	{
		printf("List is empty");
		return;
	}
	else if(count(*head)<n)
	{
		printf("invalid value");
		return;
	}
	else if(n==1)
		insertbeg(&(*head));
	else
	{
		node* temp=(*head);
		node* prev=temp;
		while(temp->next!=NULL && --n)
			{
				prev=temp;
				temp=temp->next;

			}
		prev->next=createnode(insertdata());
		(prev->next)->next=temp;

	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	int n,data,pos;
	printf("enter no of nodes in linked list1\n");
	scanf("%d",&n);
	printf("enter data part of linked list1\n");
	scanf("%d",&data);
	root->data=data;
	root->next=NULL;
	node *temp=root;
	node *temp1;
	for(int i=1;i<n;i++)
	{
		printf("enter data part of linked list\n");
		scanf("%d",&data);
		temp1=createnode(data);
		temp->next=temp1;
		temp=temp1;
	}
	print(root);
	int data1,data2;
	printf("enter 1st node\n");
	scanf("%d",&data1);
	printf("enter 2nd node\n");
	scanf("%d",&data2);
	node *res=swap(root,data1,data2);
	print(res);
	return 0;
}