March 17, 2014

Building a WAV player, part 2

This is the continuation of my last post. Here is the source code we had last time, minus the huge array which you can find in the previous post:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdint.h>
#include <avr/io.h>
#include <avr/pgmspace.h>
#define F_CPU 8000000UL  // 8 MHz
#include <avr/delay.h>
#include <avr/interrupt.h>
volatile uint16_t sample = 0;
volatile int sample_count;
const uint16_t helloworld_length= 25000;

void init_pwm(void)
{
 CLKPR = (1 << CLKPCE);
 CLKPR = 0;
    // use OC1A pin as output 
    DDRB = 1 << PB1;

    /*
    * Use timer 1 for fast PWM, 8bit
    */
    
    /*
    * Prescaler: clk/1 = 8MHz
    * PWM frequency is 8MHz / 256 = 31.25kHz
    */
    
 TCCR1A = (1 << COM1A1)| (1 << WGM10);
 TCCR1B = (1 << WGM12) | (1 << CS10);
   
    OCR1A = 0;
 
    /* Setup Timer0 which changes the pwm duty cycle in its overflow interrupt */
 
    TCCR0B |=(1<<CS00);
    TCNT0=0;
    TIMSK0|=(1<<TOIE0);
    sample_count = 4;
    sei(); //Enable interrupts
}



ISR(TIMER0_OVF_vect)
{
  
         sample_count--;
         if (sample_count == 0)
            {
             sample_count = 4;         
             OCR1A = pgm_read_byte(&helloworld[sample++]);
             if(sample>helloworld_length){
     sample=0;
    }    
            }
}



int main(void)
{
   init_pwm();
   while(1);//do nothing
}


Now what does the code do? For definiteness, let us say the speaker is connected between 5V and ground. The huge array in the previous post is a small WAV file - a really low-quality one, at a sample rate of only 8 KHz and 8-bit encoding. For comparison, CD quality is 44 KHz at 16 bit encoding. A WAV file is just a long list of numbers, encoding the form of the soundwave we want to generate. Basically, the n-th number in our array is the sound pressure after n/8000 seconds since we use a 8 KHz WAV.

To reproduce the soundwave, we now just have to apply the correct votlages at the correct times: If the n-th number in our array is 0, there should be no voltage over the speaker, if it is 255, there should be 5V, if it is 128, we want 2.5V and so on. Our microcontroller cannot directly produce these voltages, and even if it could, it could not drive the speaker from these voltages. You could plug the number into a digital-analog-converter and then use an amplifier behind the converter to drive the speaker - this is the usual route, but requires more hardware.

We go another route, faking the voltages with PWM: When the number in our WAV file is 128, we will drive the transistor such that it is open half the time. With a suitable capacitor from the ground of the speaker to 5V (for me, 22 mikrofarad seem to work best), this is nearly the same as applying 2.5 V to the speaker directly.

We have to change the PWM duty cycle 8000 or even 16000 times per second, so each sample from the WAV file will be used in the duty cycle only a few times. Let us check the math for 8000 samples per second: We want to vary the PWM duty cycle between 0 and 255, so the length of one complete cycle has to be at least 256 clock cycles. If we want to use each sample only 4 times, we need 1024 clock cycles. Since we have to do it 8000 times per second, we already need an 8 MHz clock.

The above program does exactly that: the first two lines in the pwm_init() function


CLKPR = (1 << CLKPCE);
CLKPR = 0;

set the clock rate to 8 MHz. The next four lines set Pin B1 as output, which is the pin we can directly attach to timer 1 as a PWM pin, and set up timer 1 such that it is indeed in PWM mode and sets the duty cycle to 0 - the OCR1A register contains the duty cycle. Then we set up timer 0 to create an interrupt every 256 cycles. In the interrupt handler


ISR(TIMER0_OVF_vect)
{
  
         sample_count--;
         if (sample_count == 0)
            {
             sample_count = 4;         
             OCR1A = pgm_read_byte(&helloworld[sample++]);
             if(sample>helloworld_length){
     sample=0;
    }    
            }
}

we count down from 4 since we want to use each number in the WAV file four times. Once we have reached zero after 4 interrupt handlers, i.e. after 1024 clock cycles, we pass to the next number of the WAV file and make it our dutycycle for the next four PWM cycles, and so on. Finally, when we have reached the end of the WAV file, we start again at the beginning. The pgm_read_byte function is necessary since we had to store the helloworld-array in the flash memory since it is way too large for the RAM; this is what the PROGMEM keyword in the declaration of the array was for. The function is contained in the pgmspace.h header.

Now we can play actual soundfiles, but we are extremely restricted by memory: Even at 8 KHz, we can realistically at most fit 3.5 seconds of sound into 32 kB flash memory; that is not terribly useful. The easiest way for accessing more memory is via SD cards; in the next post, I will explain how to attach an SD card to our simple player.

March 9, 2014

Building a WAV player

I have a simple 8 Ohm speaker which has been gathering dust for quite a while, so I figured I should start using it in some way. The most obvious project was building a simple WAV player, which actually turned out to be simpler than I expected.

 You will need some mikrocontroller with PWM capabilities and SPI (not very hard requirements); I will use an Atmega328p since a) I have some lying around and b) they are the controllers used in the Arduino, so you can use the Arduino hardware, which is really convenient for debugging since it has an integrated UART-USB-converter. However, we will program in C, bypassing the Arduino IDE and libraries - after all, including a library and calling a "play_wav()" function is not very teaching.

On the hardware side, besides the mikrocontroller and the speaker, you will need:
- A bipolar npn transistor.
- A resistor, depending on the amplification of your transistor - 470 Ohm should easily do it. For the beginning, you may also want to use another resistor to limit the current through the speaker, just to be on the safe side.
- An SD card for storing the WAV files and some way to connect it to your breadboard. You can for example use a micro SD card, plug it into a microSD-to-SD adapter and then solder wires onto the adapter.
- SD cards DO NOT WORK with 5V. If your microcontroller runs with 5 Volt, you need a level shifter.
- some capacitors are useful to improve sound quality.
- some wires.

Let us start with the wiring of the speaker. It is fairly simple: Connect one side of the speaker to the supply voltage, the other side to ground via the collector and emitter of the transistor. Then connect the base of the transistor via a resistor to the PWM pin on your mikrocontroller you want to use, and we are done.




 Now we can already play some simple sounds. We only have to toggle the PWM pin at an audible frequency, say something between 200 and 1000 Hertz. You can either achieve this by setting up suitable delays or timers and switch the pin whenever a delay or timer runs out; that approach has the advantage that you can create arbitrary frequencies. Since we will later on have to use the PWM functionalities anyway, we will use a dedicated PWM pin. For this part, you should add a small resistor between the speaker and VCC - the sine wave sound we will play can be quite loud.

Here is the source code for the Atmega328 used on the Arduino, taken right from Atmel Studio:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <avr/io.h>

int main(void)
{
    DDRB = (1 << PB1);
    OCR1A = 128;
    TCCR1A = (1 << COM1A1) | (1 << WGM10);
    TCCR1B = (1 << WGM12) | ( 1 << CS12);
 
    while(1)
    {
       
    }
}

Pin B1 (or Pin 9 on the Arduino) is the PWM pin for timer 1; we set timer 1 to 8-bit PWM mode by setting WGM10 and WGM12, and setting CS12 sets the prescaler to 256. Finally, the OCR1A register contains the length of the duty cycle; we set it to 128 so that the pin is high half of the time.
These settings correspond to a frequency of

16 MHz (frequency of the Arduino) / (256 (length of a PWM cycle) * 256 (prescaler)) = 244 Hz

If you are using an Atmega328p, you probably have to tweak these numbers since it may not be clocked at 16 MHz. By default, the internal oscillator clocks the Atmega at 1 MHz, so using a prescaler of 16 instead of 256 should play the same sound.

Compiling the code and uploading it, you should hear the speaker make a  - rather unpleasant - tone. In case you don't know, you upload the hex file to the Arduino by navigating to the directory containing the hex file via the command line and then executing the following command while pressing Reset on the Arduino:


avrdude -P com3 -p m328p -c avrisp -b 115200 -F -U flash:w:<NameOfYourFile>.hex

Ok, we have (hopefully) sound - even though its rather annoying sound at this point...

Before explaining what we have to do to play actual sound, let me show you a program for the Atmega328p which plays actual sound. Wiring is as before, except that you should remove the resistor between speaker and VCC.  If you want to run this code on an Arduino, you have to account for the higher frequency (16 MHz), compared to the 8 MHz of the internal oscillator of an Atmega (I remove the standard prescaler of 8 in the first two lines of main(), switching from default 1 MHz clockrate to 8 MHz). Just change all lines "sample_count = 2" into "sample_count = 4" and you should be fine. The PWM pin used is Pin B1, or Pin 9 on the Arduino layout.

Be careful when copying this program - the array extends quite far to the right.


#include <stdint.h>
#include <avr/io.h>
#include <avr/pgmspace.h>
#define F_CPU 8000000UL  // 8 MHz
#include <avr/delay.h>
#include <avr/interrupt.h>
volatile uint16_t sample = 0;
volatile int sample_count;
const uint16_t helloworld_length= 25000;



const unsigned char helloworld[] PROGMEM=
{
 116,97,48,52,0,0,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,127,128,128,128,128,128,129,128,128,128,129,128,128,128,129,128,128,128,128,128,128,128,128,128,128,128,128,127,127,128,129,128,128,128,128,128,127,128,128,127,128,128,129,129,129,129,128,127,127,127,127,129,130,129,128,127,127,128,128,127,128,129,128,128,128,128,129,129,129,129,128,127,126,127,129,129,129,128,128,128,
 126,126,127,129,130,128,128,128,126,127,129,129,127,127,128,129,128,128,129,129,127,125,128,128,127,128,130,130,128,127,127,127,127,127,129,129,129,129,129,128,128,128,129,128,126,127,128,128,127,127,130,132,129,126,127,129,128,125,127,128,130,128,127,128,128,128,127,127,128,128,128,127,127,128,129,130,130,128,128,127,126,128,128,128,130,130,129,128,126,126,126,127,132,130,127,127,128,131,127,127,
 132,132,127,122,124,129,130,128,127,130,129,125,125,127,128,129,128,129,128,128,127,127,128,128,129,129,128,127,127,129,127,128,127,128,130,129,129,128,128,127,127,129,129,128,129,129,129,127,127,128,128,128,128,128,128,127,126,129,128,127,129,130,129,126,126,127,128,127,128,131,130,127,126,126,128,129,125,127,130,131,128,127,129,128,128,125,126,130,129,131,130,130,129,125,128,129,131,130,127,130,
 129,128,128,127,129,128,126,126,127,129,126,126,128,126,125,124,127,128,127,129,129,128,126,126,127,127,127,130,134,132,129,129,129,129,127,127,131,133,131,128,130,133,132,129,129,128,127,125,124,128,131,127,126,126,125,124,123,125,124,124,124,124,124,121,122,125,126,125,125,128,128,127,126,129,131,131,135,136,137,137,135,138,138,138,138,140,143,141,137,134,133,132,127,123,123,126,120,107,98,102,
 112,106,105,109,112,121,116,113,116,122,129,125,129,139,145,148,141,142,145,144,145,144,150,153,153,151,147,146,142,137,133,129,126,125,125,118,110,101,96,94,88,88,91,91,97,121,146,154,142,127,122,120,115,115,129,147,156,155,147,143,139,132,130,134,147,155,155,156,153,149,140,134,135,131,122,115,120,124,116,100,91,90,82,74,68,86,133,166,169,148,129,124,110,97,98,124,155,165,163,153,
 145,137,121,115,122,138,155,163,166,164,155,142,130,128,130,130,123,117,123,122,111,93,81,77,75,70,76,124,171,182,161,127,118,112,102,98,111,146,167,168,155,139,137,126,116,114,125,149,160,167,167,160,152,135,128,128,130,132,121,119,122,121,112,90,78,72,74,70,79,130,173,189,165,125,112,106,107,103,110,138,161,174,158,138,130,124,124,118,122,137,152,165,163,155,149,143,140,133,129,128,
 125,126,124,118,112,102,93,84,75,69,75,112,155,185,181,148,120,101,100,106,113,127,140,157,160,154,141,125,119,116,123,130,137,145,149,153,151,150,147,142,137,132,131,129,128,123,117,114,108,101,88,77,67,76,114,159,189,180,147,115,98,103,111,120,126,137,150,158,157,142,126,116,116,124,132,138,141,146,151,156,155,149,139,131,128,128,129,125,116,110,105,102,94,85,73,74,105,146,181,182,
 155,122,101,102,112,124,128,132,139,148,155,150,138,122,116,119,129,138,141,143,147,154,157,153,143,131,125,125,128,125,117,109,101,98,92,86,76,80,108,146,178,180,157,124,103,101,111,125,129,133,136,144,152,152,142,127,117,117,126,137,143,144,145,150,155,155,146,133,123,121,124,124,118,109,101,97,92,87,79,85,108,143,173,178,161,130,107,100,110,124,132,135,134,139,146,151,147,135,123,117,
 122,131,141,145,147,149,152,152,146,137,127,122,123,122,119,111,101,93,89,87,84,91,111,139,164,172,161,137,115,104,109,120,130,134,134,137,141,147,147,141,130,121,121,128,137,144,148,149,150,149,146,139,131,125,122,120,117,111,103,96,89,85,82,90,111,138,162,171,162,140,120,108,109,118,127,132,133,135,139,145,147,143,134,125,122,125,133,140,145,148,149,148,146,142,136,131,126,123,120,115,
 108,101,93,88,84,85,96,115,136,150,154,147,136,127,124,128,132,136,137,137,137,137,137,135,131,126,124,125,130,135,141,145,149,151,151,149,144,138,131,125,118,112,106,100,95,91,87,85,89,100,115,132,144,150,150,148,145,144,145,145,144,139,132,126,121,119,120,123,127,132,136,140,145,149,152,153,151,146,140,132,124,117,111,105,100,95,92,89,88,91,99,111,124,136,144,148,149,148,148,148,
 148,145,140,134,127,122,120,121,123,127,131,134,139,143,147,151,152,150,146,140,133,126,119,113,107,102,98,95,92,90,91,97,107,120,132,140,145,147,147,147,148,148,147,143,137,131,125,122,122,124,126,129,132,136,140,145,149,150,150,147,141,135,128,122,115,110,105,101,97,93,90,90,94,103,114,126,136,143,146,146,147,148,149,149,146,141,134,128,124,122,123,125,127,130,133,137,142,146,150,150,
 149,144,139,133,126,119,113,108,103,99,96,93,91,92,97,106,118,129,138,143,145,146,147,148,149,148,145,139,133,127,124,123,124,125,128,130,134,138,143,147,149,150,147,143,138,132,125,119,113,108,103,99,95,93,91,92,98,107,118,129,138,143,145,147,148,149,150,149,145,139,132,127,124,123,123,125,127,130,134,138,143,147,150,150,148,143,138,132,126,119,113,107,103,99,96,93,91,92,96,106,
 118,130,138,143,145,146,148,149,151,149,145,139,132,126,123,122,123,125,127,130,133,138,143,148,151,151,149,144,140,134,128,121,115,108,103,99,96,94,91,91,94,101,113,125,136,142,146,147,148,149,150,150,147,141,133,127,123,122,122,124,126,128,131,136,142,148,152,153,151,147,142,137,132,125,118,111,105,100,97,95,93,90,90,94,104,117,130,141,146,148,148,148,149,150,149,144,137,128,123,120,
 121,122,125,127,130,135,141,147,152,155,154,151,146,140,135,129,122,114,108,102,98,95,93,90,88,90,96,109,123,137,146,149,151,150,150,150,149,145,137,127,118,116,117,122,126,130,133,137,144,152,158,160,157,150,144,138,133,129,123,115,107,100,96,94,92,90,86,84,91,107,130,150,161,160,152,144,140,140,138,133,122,112,108,112,124,134,141,143,143,146,152,158,158,154,146,140,136,136,136,133,
 129,121,115,110,105,100,93,85,78,74,80,98,124,149,164,166,159,151,144,138,131,121,112,106,106,115,126,137,144,148,151,153,155,154,150,144,139,137,138,139,139,137,134,133,129,122,111,98,89,82,79,75,73,82,104,137,165,177,173,157,143,134,128,121,111,103,102,109,124,140,150,154,153,153,152,150,146,139,134,133,137,142,145,143,139,138,135,130,120,106,92,83,77,75,74,73,89,117,152,177,
 181,170,149,136,126,120,111,102,99,105,121,138,151,154,154,152,151,149,144,136,130,131,137,144,149,148,145,142,141,137,127,112,97,85,80,78,76,74,74,95,128,165,185,179,161,139,129,122,115,104,96,100,115,135,149,155,153,151,151,150,144,135,128,127,135,145,151,151,147,146,144,143,134,120,105,93,86,83,78,75,72,78,104,139,172,182,172,154,137,128,119,109,99,97,108,125,142,151,152,151,
 150,150,146,137,128,126,132,141,149,151,150,149,148,147,141,131,117,104,94,86,81,75,74,76,83,109,140,170,181,171,154,135,126,115,106,99,99,111,128,143,151,151,151,149,149,143,134,127,126,133,142,149,151,151,151,149,146,140,130,117,105,96,88,83,78,76,78,82,106,136,165,179,169,155,137,127,118,107,101,99,111,127,141,150,151,151,149,147,143,134,128,127,133,142,148,152,152,152,150,146,
 140,130,119,108,98,89,82,77,77,79,81,101,131,161,179,172,157,139,128,120,109,102,98,107,124,139,149,150,150,149,147,144,136,130,127,132,141,147,151,151,152,151,148,142,132,120,108,98,88,82,77,75,78,81,100,129,159,179,174,160,141,128,120,109,102,98,106,122,137,148,151,152,151,148,145,137,130,127,130,138,145,151,152,152,151,148,143,134,123,110,99,89,81,77,75,78,81,95,126,155,
 178,176,162,145,130,123,111,102,98,103,119,135,146,151,150,151,149,147,140,131,128,129,137,144,149,151,151,152,150,144,136,124,111,101,92,84,78,73,75,78,92,121,150,175,177,165,150,134,125,113,103,98,100,115,129,142,150,151,154,152,148,143,134,130,129,134,141,145,149,150,151,150,146,140,129,115,103,92,85,79,75,75,75,84,113,144,173,179,169,154,138,131,119,106,97,96,108,124,137,147,
 149,153,154,154,149,139,133,129,132,139,144,147,148,149,149,147,142,129,115,102,92,85,79,73,72,71,85,116,147,172,174,164,152,142,137,125,111,101,99,110,123,132,137,140,147,155,159,158,148,139,135,137,143,145,144,142,144,148,151,147,136,121,107,99,91,85,75,69,66,73,91,109,133,151,164,170,163,151,134,119,114,112,113,115,119,131,145,159,168,164,157,149,147,150,149,145,138,134,138,145,
 149,143,126,111,99,95,92,83,74,62,58,60,80,117,150,175,178,167,152,139,134,130,122,114,108,112,127,146,162,166,163,155,151,156,158,155,146,134,130,132,139,142,133,120,105,95,92,88,84,74,63,56,65,98,135,170,184,176,158,141,135,136,135,129,117,107,109,122,143,159,165,161,154,154,157,162,159,148,135,125,125,131,133,128,115,100,91,86,86,84,79,69,64,80,109,148,176,183,173,151,
 136,130,134,139,135,125,114,109,117,133,151,162,164,162,157,157,158,156,151,141,131,123,117,115,112,107,100,90,84,79,77,75,76,91,111,138,159,169,170,158,147,138,134,135,134,131,125,117,116,119,130,143,154,162,164,165,162,158,153,146,139,131,123,115,107,101,96,91,87,83,80,76,77,88,106,129,151,166,171,163,153,140,134,134,135,136,130,123,116,113,120,130,144,157,165,169,166,161,154,148,
 142,136,129,119,108,98,91,87,85,85,84,82,81,87,100,121,145,164,174,171,161,147,136,131,130,132,131,129,123,118,117,120,131,145,159,170,172,169,160,150,141,134,127,119,112,102,94,87,83,81,80,81,83,91,103,122,142,160,171,172,166,154,143,133,128,126,126,126,125,123,122,122,127,136,148,160,168,172,167,159,148,136,125,116,108,101,96,91,86,83,80,78,80,88,101,121,142,160,171,173,
 168,157,145,135,129,127,127,127,127,125,122,121,123,129,139,151,161,168,169,164,154,143,129,118,108,101,97,93,91,88,85,82,81,85,95,112,131,151,166,174,173,165,154,142,132,127,125,126,128,129,128,126,124,125,129,137,147,156,163,165,161,152,140,126,112,101,94,90,90,90,91,90,89,90,94,104,119,137,154,167,174,173,166,155,142,131,124,121,121,124,126,128,129,129,130,133,138,144,150,155,
 157,155,148,138,124,111,100,92,90,90,92,94,96,97,100,105,112,124,137,149,159,165,167,162,155,145,136,128,123,122,122,124,126,129,131,133,136,138,142,145,147,148,146,141,133,123,114,105,99,96,95,95,96,98,101,105,112,119,128,137,146,152,156,157,155,151,145,139,133,129,126,125,124,125,126,128,131,134,137,140,142,143,143,141,137,131,124,118,113,109,106,104,103,101,101,102,105,109,115,123,
 131,138,145,149,152,152,150,146,142,138,134,131,128,127,126,126,127,128,130,133,135,138,139,140,139,137,133,129,125,120,116,113,111,109,107,106,106,106,108,112,116,122,128,134,139,143,146,147,146,144,142,139,136,133,130,128,127,126,127,128,130,133,135,136,137,138,137,136,133,130,127,124,121,119,116,114,111,109,107,106,107,109,113,117,123,128,134,138,142,144,145,144,143,142,139,137,134,132,130,129,
 128,128,129,130,132,133,134,134,134,134,132,131,129,127,125,122,120,118,116,114,112,110,108,108,109,111,115,120,125,130,135,138,141,143,144,144,143,141,139,137,134,132,130,129,129,130,132,133,134,135,135,135,134,133,131,129,127,125,123,120,118,115,113,111,109,108,108,109,111,115,119,125,130,134,138,140,142,142,141,140,138,136,135,133,132,131,131,131,132,134,135,136,137,137,137,135,134,132,129,127,
 125,123,121,119,116,114,112,110,108,107,107,108,112,118,124,130,136,140,143,144,143,140,138,135,132,130,129,128,128,128,129,130,132,134,137,139,141,142,141,139,136,132,128,124,122,120,119,118,117,115,112,110,107,105,105,107,112,119,127,135,141,145,146,144,142,138,136,133,132,131,130,129,128,127,127,127,129,133,137,142,146,147,146,143,137,132,126,122,119,117,117,116,115,113,110,106,103,101,103,107,
 115,125,135,142,147,148,145,141,137,133,131,131,131,131,130,129,127,126,126,129,133,138,144,148,150,148,144,138,131,125,121,119,118,117,116,115,112,108,104,100,97,100,106,116,128,140,148,152,150,145,138,133,129,128,130,131,132,132,129,127,125,126,129,135,142,148,152,152,148,141,134,128,123,121,119,119,119,117,114,109,104,99,95,94,99,109,121,135,147,153,154,150,142,135,130,128,128,131,132,131,
 129,126,124,125,128,134,142,149,153,153,149,143,135,129,125,123,122,122,121,118,114,110,104,99,96,94,96,104,116,130,144,153,155,152,145,136,130,127,127,129,131,131,129,127,124,125,129,135,143,149,153,153,149,143,135,129,126,124,124,123,122,119,114,109,104,98,94,91,92,100,114,130,146,157,160,155,145,134,127,124,126,129,131,131,128,125,123,125,130,139,146,152,153,151,145,139,134,130,128,127,
 127,126,124,120,116,111,107,101,95,91,88,93,106,123,142,157,163,158,148,136,127,123,125,129,131,131,128,123,122,125,131,140,148,152,152,149,144,139,135,132,130,129,128,126,124,122,119,114,109,103,95,89,86,88,100,120,140,157,165,161,149,136,127,123,125,129,131,129,126,122,122,126,135,143,148,151,149,145,142,139,137,135,133,130,128,128,126,125,123,118,111,105,97,89,84,84,92,110,132,152,
 164,164,154,141,130,125,125,127,129,127,124,122,123,128,135,142,146,147,145,143,142,141,141,138,135,131,128,128,130,130,127,123,116,107,100,94,88,84,84,94,114,138,157,167,165,152,137,126,122,123,127,128,125,122,122,125,132,140,146,147,145,142,140,140,141,141,139,134,130,129,130,132,132,129,123,115,106,100,94,88,83,83,93,113,138,159,169,165,151,136,125,122,124,127,127,124,120,120,126,134,
 143,147,146,142,138,138,139,142,142,139,134,130,130,133,136,136,131,124,116,109,104,100,95,88,82,83,97,122,148,166,170,159,142,128,121,123,127,129,126,120,118,122,132,142,147,147,141,136,134,138,143,145,142,137,131,129,132,137,139,135,127,119,113,109,106,102,94,85,78,82,100,129,155,169,168,154,137,125,124,127,130,128,123,117,116,124,135,145,148,144,138,134,134,139,144,145,141,135,130,130,
 134,139,140,135,128,120,116,113,110,105,98,88,81,81,94,117,143,160,164,156,143,132,127,128,130,128,123,119,118,123,132,141,144,142,137,135,136,139,143,143,140,135,132,133,136,139,140,136,130,124,121,119,116,110,103,95,87,84,87,98,119,141,156,159,153,144,134,129,128,128,126,122,119,120,125,133,140,142,141,137,135,137,140,142,142,140,136,134,134,136,137,138,136,132,127,123,121,117,111,104,
 98,93,89,89,95,109,129,148,157,156,148,138,130,127,128,128,125,121,119,122,128,136,142,142,139,136,136,137,140,141,141,139,135,134,135,137,137,137,134,129,125,123,121,116,110,104,100,95,92,92,97,110,128,145,154,154,146,137,130,127,128,128,126,122,121,124,129,135,139,140,138,136,137,139,140,140,139,138,136,135,136,137,136,135,134,131,128,125,123,118,112,107,103,100,96,95,96,102,115,133,
 149,154,150,141,133,128,127,128,128,125,121,121,126,132,138,141,141,138,135,136,138,139,139,138,137,135,135,136,137,136,135,134,131,128,125,122,118,112,107,103,101,98,97,98,103,114,131,146,152,149,141,134,128,126,127,128,126,124,124,128,132,136,138,139,138,136,136,138,139,138,137,137,136,136,136,137,136,135,134,132,129,126,123,120,115,109,106,104,102,99,99,101,107,119,136,148,150,144,136,130,
 127,126,129,129,126,123,125,130,134,137,138,138,137,136,137,138,138,137,136,136,136,136,137,137,136,135,134,132,128,124,122,119,115,112,110,108,104,101,100,101,105,116,132,144,148,144,137,132,128,128,129,129,127,124,125,129,134,136,137,137,136,136,137,138,138,137,136,137,137,137,137,137,136,134,133,132,129,126,123,121,116,112,110,109,107,103,100,100,103,111,125,141,148,145,138,133,129,128,128,129,
 128,125,124,129,134,137,137,135,135,135,136,138,139,138,136,136,137,138,137,136,135,135,134,134,132,128,124,121,119,116,113,112,110,107,102,99,99,102,112,128,142,147,144,138,132,129,127,128,128,127,125,127,131,135,136,135,134,134,136,138,139,138,137,137,138,138,137,137,136,135,135,136,135,131,126,124,123,121,117,114,111,109,106,105,104,102,101,106,121,138,147,147,141,134,129,127,128,129,128,125,
 125,129,135,137,137,134,132,133,137,140,140,137,136,136,137,138,138,137,135,135,136,136,133,128,124,123,121,119,117,115,112,108,106,105,102,99,100,111,127,143,150,146,138,131,127,127,128,128,126,124,127,132,137,138,136,132,131,134,138,139,137,136,136,138,140,140,138,135,134,135,136,136,132,127,124,123,122,120,117,115,113,111,109,105,101,98,99,108,125,142,150,147,139,132,128,126,126,126,124,124,
 127,133,137,138,136,133,130,132,137,138,136,135,136,138,140,141,139,135,134,135,137,136,133,128,125,124,124,122,119,116,113,112,111,109,105,101,98,101,114,132,146,149,144,137,130,126,126,127,125,124,125,130,135,138,138,135,131,130,133,137,137,136,135,137,139,141,140,137,135,134,136,136,135,132,127,125,125,123,121,118,116,114,113,111,108,104,100,99,103,116,133,146,148,144,137,130,126,125,124,123,
 124,127,131,135,138,138,134,131,131,133,135,137,136,136,138,140,141,140,137,135,134,135,136,134,130,126,125,125,123,122,119,116,114,113,111,108,105,101,100,103,115,131,144,149,146,138,130,125,123,122,123,125,127,131,135,138,138,136,132,130,130,132,135,137,138,139,140,141,140,139,136,134,134,135,134,132,129,127,126,124,122,120,117,115,114,112,109,106,102,100,100,107,122,137,147,150,144,134,127,123,
 122,123,124,125,128,133,137,139,138,134,131,129,129,132,135,137,139,139,140,141,141,138,136,134,134,135,134,131,129,126,124,124,122,121,118,116,113,112,109,106,104,101,101,108,122,136,148,150,144,135,127,122,121,123,124,126,128,132,136,139,138,135,131,129,129,131,134,136,138,139,140,142,142,140,137,134,133,133,133,132,130,128,126,124,122,120,118,116,114,113,111,109,106,103,102,105,115,128,141,149,
 147,140,132,124,122,122,124,126,128,130,133,136,138,137,134,131,129,130,133,135,137,139,140,140,140,139,137,135,134,134,134,133,131,128,126,123,122,120,119,118,116,115,112,110,108,105,105,105,111,123,134,145,148,144,137,128,123,122,122,126,128,129,132,133,136,137,136,134,131,130,131,133,136,138,140,141,140,139,137,135,134,133,133,133,131,130,128,125,124,122,120,119,117,116,114,112,110,108,107,106,
 107,114,124,135,144,146,143,135,127,122,121,124,127,129,131,132,133,134,135,135,133,131,130,131,134,136,140,141,141,139,136,135,134,134,135,134,132,130,128,127,125,124,121,119,117,116,116,115,113,111,109,108,107,110,117,127,138,144,145,141,133,126,122,122,125,128,130,131,132,133,133,134,134,133,132,131,132,133,136,138,140,140,138,136,134,133,134,134,134,133,130,129,126,125,123,121,119,118,117,117,
 116,114,112,110,108,107,111,117,127,136,143,145,141,134,127,123,122,124,127,130,131,132,132,133,133,133,133,132,132,132,133,135,137,139,139,138,136,134,133,133,134,134,133,131,128,126,125,123,121,120,119,118,118,117,115,113,111,110,109,112,117,125,133,139,142,140,136,130,125,123,124,127,129,131,132,132,132,132,132,132,132,132,132,132,134,136,138,139,138,136,134,132,132,133,134,133,132,129,127,125,
 123,122,121,120,120,118,117,116,114,112,111,111,111,116,122,129,136,140,141,138,133,127,124,123,125,128,130,132,132,132,132,132,132,132,132,132,132,133,135,136,138,138,137,135,133,132,133,133,134,133,131,128,126,124,123,122,121,120,119,118,117,116,114,112,111,111,113,118,124,132,138,141,140,136,131,126,124,124,126,128,130,132,132,132,132,132,132,132,132,132,133,135,136,137,138,136,135,133,132,133,
 133,134,133,132,129,127,124,123,122,121,120,119,118,117,116,114,113,112,112,113,117,122,129,135,140,140,137,133,128,125,124,125,128,130,132,132,132,131,131,132,132,132,132,132,133,134,135,137,138,137,135,134,133,133,134,134,133,131,128,126,123,122,121,121,120,119,118,117,116,114,113,112,112,114,118,125,132,137,141,140,137,131,127,124,124,126,128,130,131,132,132,132,132,132,132,132,132,132,133,134,
 136,137,137,137,135,133,132,132,133,133,133,130,128,125,123,122,121,120,119,118,117,116,115,114,113,112,112,115,120,127,134,140,141,139,134,129,126,125,126,128,129,130,131,131,131,131,132,132,133,133,133,133,133,135,136,137,137,136,134,133,133,133,134,133,132,129,126,124,123,121,120,120,119,118,117,116,115,113,113,112,114,118,124,131,137,140,139,136,131,128,126,125,127,128,129,130,130,130,131,131,
 132,133,133,133,133,132,133,134,135,136,137,136,135,134,133,133,133,133,131,129,126,124,123,122,121,120,118,117,116,115,114,114,113,113,115,119,125,132,137,140,139,135,131,128,126,126,127,128,129,129,129,130,131,132,132,133,133,133,133,133,134,135,136,136,135,134,134,134,134,134,134,133,130,128,125,123,122,121,120,119,118,117,116,116,115,114,113,114,117,122,128,134,138,138,136,133,130,128,127,128,
 128,129,129,129,129,130,131,132,133,133,134,133,133,134,135,135,135,135,134,133,133,134,134,134,133,131,129,126,124,123,121,120,118,117,116,116,115,115,115,115,116,118,122,127,131,135,136,136,134,131,129,128,129,129,129,129,128,129,129,130,131,132,133,133,133,134,134,135,136,135,135,134,133,133,133,134,134,133,131,129,127,126,124,122,120,118,117,116,116,116,115,115,115,115,117,121,125,130,134,136,
 136,134,132,131,130,130,129,129,128,128,128,129,130,131,132,132,133,133,134,135,136,136,136,135,133,133,132,132,133,133,132,131,129,128,126,124,122,120,119,118,117,116,116,115,115,115,116,118,121,125,129,132,134,134,134,133,132,131,130,130,129,128,128,128,129,130,131,131,132,133,133,135,136,136,136,136,134,133,133,132,132,132,132,131,130,129,128,126,125,123,122,121,120,119,118,118,117,116,116,117,
 118,120,123,126,129,131,133,133,133,133,132,132,131,130,130,129,129,129,129,130,130,130,131,131,132,133,133,133,133,132,132,131,131,130,130,130,130,129,129,128,128,127,126,126,125,125,124,124,124,124,124,124,123,124,124,124,125,125,126,126,127,127,128,128,128,129,129,129,130,130,130,130,130,130,130,130,130,130,130,130,130,129,129,129,129,129,129,129,129,129,129,128,128,128,128,128,128,128,128,127,
 127,128,127,127,127,127,127,127,127,127,127,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,127,128,127,128,127,128,134,131,128,127,127,128,127,127,127,128,127,127,127,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,127,128,127,127,127,127,127,127,127,127,127,127,127,127,127,128,127,136,139,134,131,128,128,125,125,126,127,128,127,126,125,128,128,127,128,128,130,129,129,128,
 127,129,128,127,127,127,127,127,127,129,129,130,131,131,130,129,128,127,126,125,126,126,127,127,127,128,129,129,129,130,130,129,128,128,128,127,127,127,127,128,128,128,128,128,129,128,128,128,128,128,127,127,127,128,128,128,128,128,129,129,129,129,129,129,128,128,128,128,128,127,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,127,127,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,127,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,127,128,129,128,128,127,128,129,128,128,128,128,128,128,129,128,128,127,128,128,128,128,128,129,128,127,128,128,128,128,128,127,127,128,128,128,
 128,129,128,127,127,128,129,128,127,127,128,129,129,128,127,127,128,128,128,128,128,128,129,128,128,129,129,128,127,127,129,128,129,130,129,126,126,128,128,128,128,128,128,127,128,130,129,126,128,131,127,125,127,132,132,125,124,127,129,130,129,126,123,126,132,132,125,123,127,132,130,127,132,132,124,124,128,130,129,130,132,127,123,126,135,132,123,127,129,126,126,127,126,128,131,131,129,128,127,125,
 123,125,130,131,130,127,125,130,133,133,129,118,122,132,129,126,130,138,131,121,123,130,129,126,126,129,126,122,132,137,132,125,120,126,131,129,127,126,129,126,128,129,130,132,129,128,123,122,127,127,131,135,135,123,117,130,136,133,127,123,132,131,120,126,141,135,121,124,127,129,129,126,130,129,128,129,127,126,122,125,134,131,124,126,129,129,126,125,129,127,121,128,133,128,126,127,129,124,123,129,
 130,136,129,125,129,124,128,133,133,130,129,128,123,129,137,139,131,119,123,127,125,127,137,142,127,117,121,124,124,126,134,134,120,113,122,134,136,123,120,128,124,119,128,138,139,128,121,123,127,134,135,138,131,124,129,129,127,133,142,140,132,126,118,126,142,142,130,124,119,119,131,137,132,122,111,110,110,117,128,127,124,119,113,114,118,124,131,127,126,133,135,135,140,146,144,137,137,141,145,141,
 142,147,141,132,127,127,132,129,124,121,126,131,119,107,101,101,107,116,118,112,112,112,119,128,123,124,128,130,130,130,135,141,145,144,143,141,140,143,143,145,147,147,145,141,135,130,127,125,130,135,125,114,114,110,102,100,108,112,103,94,99,124,137,127,120,121,126,126,127,136,143,144,141,141,145,148,144,140,144,147,145,143,144,147,144,134,126,122,122,127,128,121,110,97,92,95,99,96,84,110,
 156,149,120,103,110,128,129,135,148,149,140,130,138,152,152,147,144,142,138,136,144,154,153,142,131,128,125,117,122,129,118,104,92,95,96,80,74,90,150,182,147,103,87,111,129,133,150,159,151,127,119,139,154,155,147,143,140,130,132,148,162,158,141,130,129,125,113,116,127,121,104,91,90,81,69,71,117,191,187,124,78,82,119,134,145,163,162,137,110,117,146,161,157,145,136,130,126,137,159,170,
 159,136,123,123,124,121,120,129,126,104,90,81,67,71,71,121,208,197,125,65,67,118,142,153,165,160,134,104,109,146,170,162,141,129,125,126,136,159,174,165,140,123,121,126,130,124,124,128,118,99,81,70,68,71,73,158,234,181,95,43,77,138,150,157,161,153,125,95,119,164,176,153,125,122,126,131,146,167,179,159,127,115,122,135,136,125,122,124,115,97,85,71,64,64,73,174,242,175,90,40,
 78,136,149,161,162,153,125,95,115,162,181,156,125,117,124,134,148,170,179,160,128,112,119,133,136,127,126,124,118,97,78,64,63,68,69,179,250,178,90,29,73,139,152,161,158,156,131,94,108,151,183,170,129,111,115,133,152,169,179,164,134,111,113,134,147,139,126,117,114,104,81,65,65,66,57,147,251,212,111,23,45,128,161,163,155,154,143,106,98,132,171,181,148,115,109,123,148,169,178,170,
 142,117,110,125,144,146,137,121,110,104,88,70,60,67,57,103,223,237,158,55,19,91,148,169,162,151,153,125,100,111,148,184,169,130,106,110,138,164,178,177,158,130,107,110,133,152,149,130,111,105,93,75,60,57,64,74,181,248,194,102,17,52,126,163,172,152,152,144,114,106,124,160,176,153,123,107,122,151,172,178,167,146,122,111,119,138,148,141,125,111,101,82,68,55,58,56,110,227,236,168,
 58,13,79,140,177,164,147,154,138,119,107,125,162,175,155,117,105,126,160,182,178,159,135,117,113,122,139,149,144,123,100,84,74,65,58,53,61,164,242,221,132,27,33,93,156,177,154,152,151,143,123,107,129,156,170,150,117,112,134,170,184,170,147,126,122,121,126,134,139,141,125,106,79,62,54,60,56,83,183,230,213,116,33,41,93,162,171,155,148,147,153,132,120,121,137,160,149,134,121,140,
 170,178,169,138,125,123,127,131,128,133,131,126,107,78,61,49,62,54,101,184,220,208,114,52,44,90,153,165,162,145,149,156,144,132,115,124,142,150,147,135,143,157,170,166,145,130,121,126,129,131,131,126,124,109,91,73,55,53,45,85,161,211,216,146,80,48,72,128,155,164,149,148,155,156,150,125,116,120,137,152,154,155,150,154,155,151,143,131,125,122,124,126,125,122,112,98,82,65,60,48,
 70,132,186,213,172,115,67,66,106,140,162,152,145,146,155,162,148,129,113,117,137,155,164,156,148,145,147,150,144,132,119,115,120,127,127,119,102,87,73,68,62,60,100,146,191,192,154,106,71,84,113,148,158,151,142,140,154,161,156,135,116,114,130,156,168,164,149,137,137,142,145,137,124,114,113,120,124,120,104,88,72,66,61,71,108,147,180,178,152,114,88,93,112,140,151,151,143,141,149,155,
 157,143,128,118,124,142,158,165,157,145,135,133,137,138,135,125,117,114,115,117,111,100,84,72,62,63,91,128,167,179,165,134,102,94,103,128,145,153,147,139,140,145,155,155,147,132,122,126,137,154,162,159,147,134,129,128,134,135,132,124,115,109,105,104,101,91,79,63,63,89,127,167,180,170,136,104,91,100,126,148,158,150,138,132,136,149,158,157,144,128,121,125,141,156,164,157,143,128,121,126,
 134,140,136,124,110,101,99,99,97,90,76,64,73,99,140,170,181,165,131,103,90,102,125,150,162,157,145,132,130,138,150,157,152,140,127,124,131,145,157,159,151,136,125,121,125,132,135,131,121,108,96,88,84,82,77,75,87,106,136,159,171,164,141,118,100,100,114,136,154,161,157,145,135,131,136,144,148,148,141,135,132,136,142,148,150,145,139,132,129,128,128,127,123,117,105,94,85,78,74,70,
 80,98,124,150,165,168,152,131,111,101,108,123,143,155,159,153,142,134,132,137,143,146,145,140,136,134,137,141,145,146,144,140,136,134,132,130,128,122,115,104,93,84,77,73,68,77,95,121,149,165,170,156,136,116,104,108,120,138,151,157,154,144,137,133,136,141,144,145,141,138,135,137,140,143,145,143,141,139,137,136,133,130,123,115,105,93,84,77,74,70,73,89,111,139,160,169,163,144,125,109,
 107,116,131,146,153,153,146,139,135,135,141,144,145,141,136,134,135,139,144,146,146,143,140,139,138,137,133,127,119,111,100,90,82,76,72,68,74,92,117,146,165,171,160,139,120,108,110,121,136,148,151,147,140,135,136,140,145,147,142,135,129,130,135,143,149,150,146,141,138,139,141,142,137,130,120,110,101,92,85,78,74,69,69,84,108,139,163,172,165,144,123,111,110,122,135,145,147,142,138,135,
 139,145,147,146,139,130,125,127,136,146,152,152,146,140,137,139,144,146,143,134,124,115,107,101,92,84,74,67,62,68,93,124,155,172,170,153,130,116,113,120,133,140,141,138,134,136,141,149,152,147,137,125,119,121,131,144,152,155,151,143,140,140,144,148,146,141,132,124,118,113,106,97,85,73,65,62,64,85,116,146,168,169,157,137,121,118,121,130,136,135,133,133,138,147,152,153,144,131,121,116,
 121,131,141,149,150,149,147,146,147,147,146,144,140,137,132,127,121,113,104,93,82,74,67,64,63,82,114,146,170,171,157,136,120,120,125,131,135,130,128,133,143,155,157,151,137,122,116,116,123,133,139,144,148,151,153,152,150,146,142,142,142,141,137,130,123,116,109,102,91,80,70,63,62,67,95,130,158,172,163,146,131,123,127,128,127,126,124,133,146,155,159,149,136,124,117,118,119,122,128,136,
 148,157,161,159,153,148,146,144,144,140,134,130,126,124,121,116,109,99,91,85,81,80,80,90,105,116,125,129,133,140,147,152,150,143,136,132,135,139,138,133,123,113,111,115,125,138,150,157,161,163,162,159,154,146,137,129,122,121,125,130,133,132,126,118,112,107,103,99,92,83,74,69,72,92,122,150,172,179,169,155,142,133,130,130,125,115,107,102,104,118,136,151,162,166,163,160,158,154,149,143,
 134,125,123,126,132,139,142,137,130,122,116,112,108,99,88,78,71,68,71,84,109,138,163,178,178,164,146,132,123,121,121,117,111,108,110,119,135,150,158,160,158,154,152,152,151,146,139,131,127,130,137,143,146,143,135,128,123,119,115,108,97,87,81,78,79,81,86,101,121,139,154,166,165,155,143,129,116,112,114,114,117,122,125,132,145,155,158,156,147,136,132,136,140,144,146,145,144,146,147,145,
 141,135,129,126,124,118,109,100,92,86,86,89,87,81,78,100,144,181,192,177,142,106,95,105,119,128,127,120,120,137,159,167,159,140,119,113,124,139,149,155,154,151,150,149,143,135,131,131,134,134,125,111,100,95,93,94,92,86,77,69,85,135,182,198,182,146,107,93,106,121,126,123,118,119,137,160,168,155,137,121,116,125,139,145,147,150,154,155,154,145,132,126,131,138,139,130,114,101,98,100,
 98,93,85,77,69,77,117,167,192,184,157,122,100,103,117,123,121,119,121,133,153,165,158,141,126,120,123,133,141,143,146,153,157,154,147,136,128,130,139,142,135,121,108,102,102,105,100,89,80,76,73,87,130,173,187,173,147,118,103,109,121,122,119,120,126,139,154,161,151,135,126,125,128,134,140,142,147,155,157,151,140,133,131,135,141,139,127,114,108,107,106,103,94,84,79,79,79,97,140,177,
 181,163,140,116,105,112,124,124,119,122,130,141,153,157,145,131,127,128,131,137,142,144,147,153,154,146,137,132,133,137,141,138,126,113,109,108,106,101,95,87,81,80,82,100,140,174,179,159,136,117,109,115,125,125,119,121,131,143,151,153,144,131,127,131,134,137,140,144,147,151,151,145,135,132,135,140,141,136,125,114,110,111,108,101,93,87,83,83,83,97,133,168,177,161,140,121,112,116,125,126,
 121,120,128,140,149,152,146,134,128,130,135,138,139,142,145,148,149,145,138,133,135,139,141,136,127,117,111,110,108,103,95,89,86,86,84,93,123,159,174,162,143,126,117,117,125,128,122,119,125,136,146,150,147,138,131,131,135,138,139,141,144,146,147,144,139,135,134,138,141,138,129,120,114,112,110,105,99,93,89,88,87,87,104,138,165,168,153,136,123,119,122,128,127,121,119,127,138,145,147,143,
 136,132,134,138,140,139,140,143,144,143,141,138,136,138,141,141,135,125,117,114,113,110,105,98,92,89,89,88,92,112,143,162,160,147,136,128,126,128,128,124,118,118,125,134,140,141,140,138,136,137,139,139,138,139,139,139,138,137,136,135,136,138,137,135,130,125,121,117,114,109,103,97,94,92,93,104,123,139,148,152,149,145,140,132,122,119,120,120,118,120,125,131,138,142,140,138,139,140,139,136,
 133,131,133,135,133,131,131,134,136,136,134,129,125,123,119,113,106,100,98,96,96,108,128,139,141,145,149,148,144,136,125,118,120,119,116,118,123,129,134,139,138,139,142,142,138,135,133,134,135,134,130,129,132,135,135,133,133,132,129,125,119,114,110,105,100,96,94,102,122,135,136,140,149,152,146,138,129,124,124,121,114,114,122,128,129,131,135,139,144,143,137,136,138,137,134,131,130,132,133,132,
 131,133,136,134,130,126,124,121,116,109,103,101,99,94,102,123,133,132,139,149,151,145,139,132,129,128,121,114,117,124,125,124,129,135,140,141,139,138,141,142,138,133,134,134,131,129,130,131,133,133,130,129,129,126,120,116,112,105,102,98,93,104,124,127,125,139,152,148,141,140,138,134,128,120,118,123,123,117,121,130,133,133,137,141,143,143,140,140,140,137,131,129,131,130,129,130,133,132,130,128,
 127,125,121,114,109,107,103,94,96,112,122,119,127,145,148,141,142,146,141,133,127,125,125,121,117,119,125,125,125,132,138,138,139,145,148,143,139,138,136,130,127,128,130,129,127,129,132,129,125,125,123,116,110,108,104,95,97,112,116,114,128,143,141,138,147,149,140,136,135,131,126,121,120,121,120,119,125,130,131,135,141,146,148,145,143,142,136,130,130,130,126,127,129,128,128,128,127,126,123,118,
 116,113,105,99,100,108,111,111,122,135,135,136,147,147,141,142,141,134,130,128,124,120,119,120,122,123,127,132,136,139,147,148,143,144,144,135,131,133,128,126,128,127,125,126,126,125,123,120,119,117,111,106,103,104,111,111,114,126,130,130,139,144,141,143,144,140,136,134,131,125,122,122,121,120,124,128,132,138,141,142,145,145,141,140,138,134,132,130,128,126,124,124,123,122,121,120,118,118,114,111,
 107,105,112,113,113,123,128,127,135,140,138,141,143,141,138,137,134,130,127,125,122,121,123,124,128,134,136,139,142,142,142,141,139,138,134,133,131,127,126,124,121,121,120,117,117,117,113,112,110,106,113,114,113,123,126,127,133,137,137,139,142,141,138,138,136,131,129,128,124,123,125,124,125,132,134,135,141,141,140,142,140,137,137,135,131,129,128,125,122,122,120,117,117,117,114,112,112,108,110,115,
 113,119,125,126,130,135,137,138,141,141,139,139,137,134,131,129,126,124,124,124,124,128,131,133,137,139,140,140,140,139,138,136,134,132,129,127,124,122,121,119,117,117,115,113,112,109,108,114,113,115,123,125,127,132,135,136,139,141,140,139,139,136,133,131,128,125,125,124,123,125,127,130,134,135,139,140,140,141,139,137,136,134,132,130,128,125,123,122,119,118,117,115,114,112,110,109,114,113,116,123,
 124,127,132,134,136,139,141,139,140,139,136,134,132,128,125,124,123,122,124,126,128,133,135,137,140,140,140,140,139,137,136,134,131,129,127,124,123,121,119,117,117,115,113,112,108,112,114,112,120,123,125,130,134,135,138,141,140,140,141,137,135,133,129,126,124,123,121,123,125,126,130,132,136,140,139,141,141,139,139,137,135,133,131,128,126,124,122,121,119,117,117,115,112,111,108,113,114,113,121,123,
 125,131,133,136,138,141,140,140,140,137,134,132,128,125,124,122,121,122,124,125,130,134,135,140,141,140,142,140,138,137,135,133,131,129,126,124,123,121,120,119,117,117,114,112,109,110,114,112,117,123,123,129,133,134,138,140,140,140,141,138,135,133,129,126,124,122,121,121,123,124,127,131,136,137,141,143,140,142,140,136,137,135,131,131,128,125,125,124,121,121,120,117,117,115,111,109,109,114,112,116,
 123,123,129,134,134,139,142,140,141,141,137,134,132,128,124,123,121,119,121,122,124,129,134,136,140,143,142,142,142,138,137,136,132,131,130,126,125,124,122,123,121,120,119,117,114,112,109,109,114,112,116,124,124,129,135,135,139,142,141,140,140,137,133,130,127,123,121,121,119,120,123,124,128,133,137,139,142,144,142,141,140,136,135,133,131,130,129,127,126,125,124,124,123,121,119,117,114,110,106,108,
 112,110,116,124,124,131,137,137,141,144,142,141,140,135,131,128,124,120,119,119,118,120,124,126,131,137,141,142,145,144,141,141,138,134,133,131,128,128,128,126,126,126,125,125,124,121,120,117,113,110,106,107,112,111,117,126,127,132,140,139,142,145,141,139,138,133,129,125,122,119,118,119,119,121,126,129,132,138,141,142,146,143,140,140,135,132,132,129,129,129,128,128,128,128,128,127,126,123,119,117,
 113,108,106,103,108,112,113,123,129,131,140,143,142,145,144,139,137,133,128,124,120,118,117,117,120,122,125,131,134,137,142,143,143,143,141,137,135,132,130,129,129,129,130,131,131,131,131,129,128,125,122,118,115,111,107,103,102,107,112,115,125,133,135,141,146,144,144,143,138,133,130,125,120,118,117,117,118,122,125,128,133,137,139,142,143,141,140,139,135,132,131,129,128,129,131,131,132,133,133,132,
 131,128,125,122,118,114,110,107,104,102,105,113,116,122,134,138,140,146,145,143,142,137,132,128,123,121,118,116,118,119,122,127,130,134,137,139,141,141,140,140,136,133,132,129,128,129,130,131,133,133,134,134,133,131,129,126,123,119,114,112,109,106,105,104,109,117,121,128,137,140,141,144,143,140,137,133,129,124,121,120,118,118,121,123,126,130,133,136,138,139,140,139,137,136,134,132,130,129,130,130,
 132,133,134,135,135,133,132,130,126,124,121,117,114,112,110,108,108,108,111,118,124,128,135,140,140,141,141,138,134,130,128,125,121,121,121,121,123,125,128,131,133,136,138,138,139,139,137,135,133,131,130,129,130,131,132,133,134,134,133,132,130,128,126,123,120,117,115,113,112,111,110,110,113,119,124,128,134,138,139,139,138,137,133,129,127,125,122,122,122,123,125,126,129,132,133,135,137,137,138,138,
 136,134,133,131,131,130,130,132,133,133,133,133,133,131,129,127,125,122,120,118,116,115,113,112,112,113,114,120,124,128,132,136,137,137,136,135,133,129,127,126,124,124,123,124,126,127,129,132,134,135,137,137,138,136,135,133,132,131,130,130,131,132,132,133,133,133,131,130,128,127,124,122,120,118,117,115,114,114,114,114,116,120,125,128,131,134,136,136,135,134,132,130,127,126,125,125,125,125,127,128,
 129,131,133,135,136,136,137,136,134,133,131,131,130,130,131,132,132,132,132,132,131,129,127,126,124,123,121,119,118,116,115,115,115,116,117,120,124,127,130,133,134,135,134,133,132,130,128,127,126,126,127,127,127,129,130,132,134,135,135,135,135,134,133,132,131,131,131,130,131,132,132,132,132,131,131,130,127,126,124,123,121,119,118,118,118,117,116,117,118,120,123,126,129,131,132,133,133,133,131,130,
 129,128,128,127,128,128,129,129,131,132,133,133,133,134,134,133,132,132,131,131,131,130,131,131,131,131,131,131,130,129,127,126,124,123,122,120,119,118,118,118,118,118,120,122,124,126,128,130,131,132,132,131,130,130,130,129,129,129,130,130,131,131,131,132,132,132,132,132,132,132,131,131,131,131,131,131,131,131,131,131,130,129,128,127,126,125,123,123,122,120,120,119,120,120,120,120,121,123,124,126,
 128,129,130,130,130,130,130,130,130,130,130,130,131,131,131,131,132,132,132,132,133,133,132,132,131,131,131,131,130,130,130,130,130,129,128,127,127,126,125,124,123,122,121,120,120,120,121,121,122,122,123,125,126,127,128,129,130,130,130,130,130,130,131,131,131,131,131,132,132,132,132,133,133,132,132,132,131,131,131,131,130,130,130,130,129,128,128,127,126,126,125,124,123,123,122,121,121,121,122,122,
 123,123,124,124,125,126,127,128,128,129,130,130,130,131,131,131,131,131,132,132,132,132,133,133,132,132,132,132,132,132,132,131,131,131,130,130,129,129,128,127,127,126,125,124,123,122,121,121,121,121,121,122,123,123,124,124,124,124,125,126,127,128,129,131,132,132,133,133,133,133,134,134,134,133,133,133,133,133,132,132,131,131,131,130,130,129,129,128,128,127,127,126,126,125,125,124,124,123,123,123,
 123,123,122,123,123,123,124,124,124,125,125,126,126,127,128,129,130,131,132,132,132,132,132,133,133,133,133,133,133,133,133,132,132,131,131,130,130,129,129,129,129,128,127,127,126,126,126,125,125,124,124,124,124,123,123,123,124,124,125,125,125,125,125,126,126,126,126,127,128,129,129,130,130,130,130,131,131,132,132,132,132,132,132,132,132,132,131,131,131,131,130,130,129,129,129,129,128,127,127,126,
 126,126,126,125,125,125,125,125,125,125,125,125,125,125,126,126,126,126,126,126,127,127,127,127,127,128,128,129,129,129,130,130,130,130,130,130,131,131,131,131,131,131,130,130,130,130,130,130,129,129,129,128,128,128,127,127,127,126,126,126,126,126,126,127,127,127,128,127,127,127,127,127,127,128,128,127,127,126,127,127,127,127,127,127,128,128,128,128,129,129,129,129,129,130,130,129,129,130,130,130,
 130,129,129,129,129,129,129,129,128,128,128,128,128,128,128,127,127,127,127,127,127,127,127,127,127,127,127,127,127,127,127,127,127,127,127,127,128,128,128,128,128,128,128,128,129,129,129,129,129,129,129,129,129,129,129,129,129,129,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,127,128,128,128,128,128,128,128,128,128,128,128,128,128,128,129,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
 128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,
};


/* initialise the PWM */
void init_pwm(void)
{
 CLKPR = (1 << CLKPCE);
 CLKPR = 0;
    // use OC1A pin as output 
    DDRB = 1 << PB1;

    /*
    * Use timer 1 for fast PWM, 8bit
    */
    
    /*
    * Prescaler: clk/1 = 8MHz
    * PWM frequency is 8MHz / 256 = 31.25kHz
    */
    
 TCCR1A = (1 << COM1A1)| (1 << WGM10);
 TCCR1B = (1 << WGM12) | (1 << CS10);
   
    OCR1A = 0;
 
    /* Setup Timer0 which changes the pwm duty cycle in its overflow interrupt */
 
    TCCR0B |=(1<<CS00);
    TCNT0=0;
    TIMSK0|=(1<<TOIE0);
    sample_count = 4;
    sei(); //Enable interrupts
}



ISR(TIMER0_OVF_vect)
{
  
         sample_count--;
         if (sample_count == 0)
            {
             sample_count = 4;         
             OCR1A = pgm_read_byte(&helloworld[sample++]);
             if(sample>helloworld_length){
     sample=0;
    }    
            }
}



int main(void)
{
   init_pwm();
   while(1);//do nothing
}

The HTML version of this sourcecode is unfortunately so large that either the blogger software or (more likely) my browser refuse to handle it properly while editing, so the explanation of the source code will be postponed to an upcoming post.