Reverse The Number

All submissions for this problem are available.

If an Integer N, write a program to reverse the given number.

Input

The first line contains an integer T, total number of testcases. Then follow T lines, each line contains an integer N.

Output

Display the reverse of the given number N.

Constraints

• 1 ≤ T ≤ 1000
• 1 ≤ N ≤ 100000

Example

Input
4
12345
31203
2123
2300
Output
54321
30213
3212
32

Solution

1. #include<stdio.h>
2. int main()
3. { int t,i,d;
4. long a;
5. scanf("%d",&t);
6. while(t--)
7. { long s=0;
8. scanf("%ld",&a);
9. while(a!=0){
10. d=a%10;
11. s=s*10+d;
12. a=a/10;
14. }
16. printf("%ld\n",s);
17. }
18. }

First and Last Digit

All submissions for this problem are available.

If Give an integer N . Write a program to obtain the sum of the first and last digit of this number.

Input

The first line contains an integer T, total number of test cases. Then follow T lines, each line contains an integer N.

Output

Display the sum of first and last digit of N.

Constraints

• 1 ≤ T ≤ 1000
• 1 ≤ N ≤ 1000000

Example

Input
3 
1234
124894
242323

Output
5
5
5

Solution

1. #include<stdio.h>
2. int main()
3. { int t,i,d;
4. long a,w=0,c=0;
5. scanf("%d",&t);
6. while(t--)
7. { long s=0;
8. scanf("%ld",&a);
9. w=a%10;
10. while(a!=0){
11. d=a%10;
12. s=s*10+d;
13. a=a/10;
15. }
16. c=s%10;
17. printf("%ld\n",w+c);
18. }
19. }

 

Lucky Four

Kostya likes the number 4 much. Of course! This number has such a lot of properties, like:

• Four is the smallest composite number;
• It is also the smallest Smith number;
• The smallest non-cyclic group has four elements;
• Four is the maximal degree of the equation that can be solved in radicals;
• There is four-color theorem that states that any map can be colored in no more than four colors in such a way that no two adjacent regions are colored in the same color;
• Lagrange's four-square theorem states that every positive integer can be written as the sum of at most four square numbers;
• Four is the maximum number of dimensions of a real division algebra;
• In bases 6 and 12, 4 is a 1-automorphic number;
• And there are a lot more cool stuff about this number!

Impressed by the power of this number, Kostya has begun to look for occurrences of four anywhere. He has a list of T integers, for each of them he wants to calculate the number of occurrences of the digit 4 in the decimal representation. He is too busy now, so please help him.

Input

The first line of input consists of a single integer T, denoting the number of integers in Kostya's list.

Then, there are T lines, each of them contain a single integer from the list.

Output

Output T lines. Each of these lines should contain the number of occurences of the digit 4 in the respective integer from Kostya's list.

Constraints

• 1 ≤ T ≤ 10⁵
• (Subtask 1): 0 ≤ Numbers from the list ≤ 9 - 33 points.
• (Subtask 2): 0 ≤ Numbers from the list ≤ 10⁹ - 67 points.

Example

Input:
5
447474
228
6664
40
81

Output:
4
0
1
1
0

Solution

1. #include<stdio.h>
2. int main()
3. { int t,d;
4. long a;
5. scanf("%d",&t);
6. while(t--)
7. { long c=0;
8. scanf("%ld",&a);
10. while(a!=0){
11. if(a%10==4)
12. c++;
14. a=a/10;
16. }
18. printf("%ld\n",c);
19. }
20. }

 

1. Find Remainder

   
   All submissions for this problem are available.
   

   Write a program to find the remainder when two given numbers are divided.

   Input

   The first line contains an integer T, total number of test cases. Then follow T lines, each line contains two Integers A and B.

   Output

   Find remainder when A is divided by B.

   Constraints

   • 1 ≤ T ≤ 1000
   • 1 ≤ A,B ≤ 10000

   Example

   Input
   3 
   1 2
   100 200
   10 40
   
   Output
   1
   100
   10

   
   

   Solutions

   #include <stdio.h>
2.  
3. int main() {
4. // Read the number of test cases.
5. int T;
6. scanf("%d", &T);
7. while (T--) {
8. // Read the input a, b
9. int a, b;
10. scanf("%d %d", &a, &b);
11.  
12. // Compute the ans.
13. // Complete this line.
14. int ans =a%b;
15. printf("%d\n", ans);
16. }
17.  
18. return 0;
19. }

Ciel and Receipt

All submissions for this problem are available.

Tomya is a girl. She loves Chef Ciel very much.

Tomya like a positive integer p, and now she wants to get a receipt of Ciel's restaurant whose total price is exactly p. The current menus of Ciel's restaurant are shown the following table.

Name of Menu	price
eel flavored water	1
deep-fried eel bones	2
clear soup made with eel livers	4
grilled eel livers served with grated radish	8
savory egg custard with eel	16
eel fried rice (S)	32
eel fried rice (L)	64
grilled eel wrapped in cooked egg	128
eel curry rice	256
grilled eel over rice	512
deluxe grilled eel over rice	1024
eel full-course	2048

Note that the i-th menu has the price 2^i-1 (1 ≤ i ≤ 12).

Since Tomya is a pretty girl, she cannot eat a lot. So please find the minimum number of menus whose total price is exactly p. Note that if she orders the same menu twice, then it is considered as two menus are ordered. (See Explanations for details)

Input

The first line contains an integer T, the number of test cases. Then T test cases follow. Each test case contains an integer p.

Output

For each test case, print the minimum number of menus whose total price is exactly p.

Constraints

1 ≤ T ≤ 5
1 ≤ p ≤ 100000 (10⁵)
There exists combinations of menus whose total price is exactly p.

Sample Input

4
10
256
255
4096

Sample Output

2
1
8
2

Explanations

In the first sample, examples of the menus whose total price is 10 are the following:
1+1+1+1+1+1+1+1+1+1 = 10 (10 menus)
1+1+1+1+1+1+1+1+2 = 10 (9 menus)
2+2+2+2+2 = 10 (5 menus)
2+4+4 = 10 (3 menus)
2+8 = 10 (2 menus)
Here the minimum number of menus is 2.

In the last sample, the optimal way is 2048+2048=4096 (2 menus). Note that there is no menu whose price is 4096.

Solution

#include<stdio.h>
#include<math.h>
int main(){
    int t;
    scanf("%d",&t);
   
    while(t--){
        int p,i,count=0,j;
        scanf("%d",&p);
        while(p>2048){
            count++;
            p-=2048;
        }
        while(p!=0){
   
        for(i=0;i<13;i++){
            if(pow(2,i)>p){
                count++;
                break;   
            }
           
        }
        j=i-1;
        p=p-pow(2,j);
       
    }
        printf("%d\n",count);   
       
    }
    return 0;
}

The Lead Game

All submissions for this problem are available.

The game of billiards involves two players knocking 3 balls around on a green baize table. Well, there is more to it, but for our purposes this is sufficient.

The game consists of several rounds and in each round both players obtain a score, based on how well they played. Once all the rounds have been played, the total score of each player is determined by adding up the scores in all the rounds and the player with the higher total score is declared the winner.

The Siruseri Sports Club organises an annual billiards game where the top two players of Siruseri play against each other. The Manager of Siruseri Sports Club decided to add his own twist to the game by changing the rules for determining the winner. In his version, at the end of each round the leader and her current lead are calculated. Once all the rounds are over the player who had the maximum lead at the end of any round in the game is declared the winner.

Consider the following score sheet for a game with 5 rounds:

    Round     Player 1       Player 2

      1             140                 82
      2              89                 134 
      3              90                 110 
      4              112              106
      5              88                  90 

The total scores of both players, the leader and the lead after each round for this game is given below:

    Round      Player 1       Player 2     Leader     Lead

      1               140             82        Player 1     58
      2               229            216       Player 1     13
      3               319            326       Player 2      7
      4               431            432       Player 2      1
      5               519            522       Player 2      3

The winner of this game is Player 1 as he had the maximum lead (58 at the end of round 1) during the game.

Your task is to help the Manager find the winner and the winning lead. You may assume that the scores will be such that there will always be a single winner. That is, there are no ties.

Input

The first line of the input will contain a single integer N (N ≤ 10000) indicating the number of rounds in the game. Lines 2,3,...,N+1 describe the scores of the two players in the N rounds. Line i+1 contains two integer Si and Ti, the scores of the Player 1 and 2 respectively, in round i. You may assume that 1 ≤ Si ≤ 1000 and 1 ≤ Ti ≤ 1000.

Output

Your output must consist of a single line containing two integers W and L, where W is 1 or 2 and indicates the winner and L is the maximum lead attained by the winner.

Example

Input:

5
140 82
89 134
90 110
112 106
88 90

Output:

1 58

Solution 

1. #include<stdio.h>
2. int main(){
3.  
4. int n,i;
5. scanf("%d",&n);
6. int a[n],b[n],lead[n],win[n];
8. for(i=0;i<n;i++)
9. {scanf("%d%d",&a[i],&b[i]);
10. }
11. int sum1=0,sum2=0;
12. for(i=0;i<n;i++)
13. {sum1+=a[i];
14. sum2+=b[i];
15. if(sum1>sum2)
16. {lead[i]=sum1-sum2;
17. win[i]=1;
18. }
20. else{
21. lead[i]=sum2-sum1;
22. win[i]=2;
23. }
24. }
25. int w=0,l=0;
26. for(i=0;i<n;i++){
27. if(l<=lead[i])
28. {
29. l=lead[i];
30. w=win[i];
31. }
32. }
34. printf("%d %d",w,l);
35. }