This chapter focuses on the essential of the research and the problem that lead to the development of this project. The objective and the significance of the project are also described in this chapter.
Research Background
Herbs are plant that is valued for flavor, scent, medicinal or other qualities other than its food value. Herbs are used in cooking, as medicines, and for spiritual purposes.(Karan et al,2002). Even before recorded history, herbs were the sources of countless culinary, medical and craft materials.
Malaysia has been known as a rich country with herbal plants. Herbal plants have been use thousand years ago by Malay and Chinese for cooking, medicine and spiritual purpose.(Mokhtar,2010). Mokhtar in his interview with Datuk Seri Noh Omar, Minister of Agriculture and Agro-based Industry that minister said Malaysia have more than 6,000 types of herbs with potential to be developed into traditional remedies for sale.
Nowadays, peoples have a difficulty to recognize the herb plants. The lack of knowledge and expert in herb makes a lot of people do not fully utilize the advantage of each herb. The unavailability of expert in herbs also makes people choose modern treatment which is more expensive.
Problem Statement
Nowadays, lack of knowledge about herb plants make most of people cannot recognize the species of herb. Sometime people look the herb plant same as other plant that have no function for disease treatment. The lack of knowledge makes people not fully utilize the usage of herb plant that available in their environment.
Day by day, lack of expert and some expert have their limit to recognize the species of herb plant make the process of recognition are not efficient. In other situation exist different result between an expert and other expert. This problem produces inconsistency result and the recognition process maybe wrong.
1.3 Research Question
Three research questions have been identified to conduct the research:
How to recognize an herb plant?
What is the best method to apply on the herb recognition?
How to use evaluate the input image by using artificial intelligent method?
1.4 Research Objective
There are three directions for this project to be achieved:
To identify suitable part from herbs plant that can be used for herb recognition
To design intelligent system for Herb Recognition System
To develop Herb Recognition System using Backpropagation neural network
1.5 Scope
This project will focus on producing an output that recognizes the species of herb. The output will be produced based on the image input. To be more specific, this project will limit to use 3 species of herbs. It is Kesum, Mas Cotek and Putarwali. The target user of this system is expert who research on herbs and people who want to use herbs as way of disease treatment.
1.6 Overview of Research
This research consists of 3 stages of methodology:
Figure 1.1: Stages of methodology
Table 1.1: Description of Methodology Stages
Stage
Description
Theoretical Study
This is the first stage of research. On this stage, process of research and finding out information about herbs plant. The purpose for theoretical study is to gain information and knowledge about herbs plant and find the best part of herb plant that can be used for herbs recognition.
Architecture Design
This stage will focus on designing the system. In this stage, the best technique to solve the problem will be determined. This stage also will come out with an algorithm of the technique chosen. Algorithm is a prototype of a new approach to be used to recognize the image and find the function of the herbs in medicine.
Evaluation
Evaluation stages are the stage to estimate the whole research and conclude the result of the solution. This stage also will conclude the research question either the new propose technique is better than the previous approach.
Significant of Research
The significant of this research is to promote a system to recognize herbs. This system is promoting an efficient and consistent recognition of herb recognition. This system also makes the process of recognition faster than current system.
.
Outline of the Thesis
Table 1.2: Thesis Chapter
Chapter
Description
Chapter 2
This chapter will conduct the specific study on the previous research paper on the research domain and propose technique.
Chapter 3
In this chapter, it will finding out all activities involve to succeeding the objective and details of all activities to achieve the research objectives
Chapter 4
This chapter will describe in details all the activities done during the empirical study phase (chapter 3)
Chapter 5
This chapter will describe the detail of the design and development process of the Herb Recognition
Chapter 6
In this chapter will evaluate and analyze the performance of the herb recognition system
Chapter 7
This chapter will conclude all the research and development activity of Herb Recognition system.
On the next chapter is a literature review. It will describe the specific study of previous research paper.
CHAPTER 2
LITERATURE REVIEW
This chapter will describe in detail the related literate to Herbs Recognition and it use in medicine. Other than that, in this chapter will explain the technique will be used on recognition and will describe the comparison between some other techniques.
Figure 2.1: Flowchart of studying on Methodology and Domain
Introduction of Herbs in Malaysia
Herbs are plant that is valued for flavor, scent, medicinal or other qualities other than its food value. Herbs are used in cooking, as medicines, and for spiritual purposes. Karan and friends in their book said even before recorded history, herbs were the sources of countless culinary, medical and craft materials.
For example Cat's Whiskers or Misai Kucing has been used for centuries in Malaysia, Indonesia and Thailand as traditional remedy for passing of kidney stones and in the treatment of urinary disorders, high blood pressure, high cholesterol, diabetes, rheumatism and gout(Yim,2010).
2.2 Study of Plant Part
Figure 2.2: Plant Part
(source: http://www.botanical-online.com/lasplantasangles.htm,2011)
2.3 Techniques (Backpropagation)
According to Rojas (1996), Backpropagation is the most widely used tool in the field of artificial neural networks. It has been one of the most studied and used algorithms for neural networks learning ever since. Rojas said Backpropagation one of the method that have capability in handling such large learning problem.
Yacob and friends (2008) in their journal said, backpropagation was created by generalizing the Widrow-Hodd learning rule to multiple-layer neural network and non-linear differentiable transfer function. They explain that both input and output vectors are used to train a network until it can approximate a function, associate input vectors with specific output vectors, or even classify input vectors according to developer definition. When backpropagation networks are properly trained, it tends to give reasonable answer when tested with inputs that they have never seen before. In their journal also state that after the neural network is trained with samples, the network weight values are changed according to the minimum value of the sum-squared error between expectation and actual output.
2.2.1 Introduction to Backpropagation
Backpropagation is a supervised learning algorithm and is mainly used by Multi-Layer-Perceptrons to change the weights connected to the net's hidden neuron layer(s).
The backpropagation algorithm uses a computed output error to change the weight values in backward direction. To get this net error, a forward propagation phase must have been done before. While propagating in forward direction, the neurons are being activated using the sigmoid activation function.
The formula of sigmoid activation is:
f(x) = 1/(1+e-input)
The algorithm works as follows:
1. Perform the backpropagation phase for an input pattern and calculate the output error
2. Change all weight values of each weight matrix using the formula weight(old) + learning rate * output error * output(neurons i) * output(neurons i+1) * ( 1 - output(neurons i+1) )
3. Go to step 1
4. The algorithm ends, if all output patterns match their target patterns
2.2.2 Architecture
This section will presents the architecture of the network that is most commonly used with the backpropagation algorithm - the multilayer feedforward network.
Figure 2.2: Backpropagation Architecture
An elementary neuron with R inputs is shown above. Each input is weighted with an appropriate w. The sum of weighted inputs and the bias forms the input to the transfer function f. Neurons can use any differentiable transfer function f to generate their output.
System Design
Figure 2.3: Application Design (Radej, 2009)
From the figure 2.3, Radej proposed a design for Plant identification system by morphology of leaf using support vector machine. He aims to create a tool assist to reduce the time it takes to identify various kinds of plants and also to reduce any errors from eye detection and human recognition. All such kinds of sample plants are stored in-form of digital image and then transform to binary data format by image-processing technique involve with seven characteristics of plants.
Related Works
2.3.1 Backpropagation in different domain
2.3.1 [a]: Harum Manis Mango Weevil Infestation Classification Using Backpropagation Neural Network.(Yacob et. al., 2008)
Yacob & friends has state that many research has been done to determine the fruit quality. Their give some example that one of research determine apple quality by using MRI and dielectric properties. Yacob & friends add, the present quality control system of mango in Malaysia is carried out manually. In other fields, they state that using dielectric and MRI for determination quality are not suitable for some environment and temperature. So Yacob propose backpropagation for classify the quality of mango from the data recorded by dielectric sensors.
2.3.1 [b]: A Backpropagation Neural Networks for Grading Jatropha curcas Fruits Maturity
(Effendi et. al., 2010)
According to Effendi and friends, the quality of Jatropha curcas can be know from type, size and skin color. This research was initially planned to be completed in two stages. The first stage is to extract the characteristics from the pattern being studied and second stages are to recognize the pattern. Effendi adopt back propagation algorithm neural network because it's fast and has a simple structure. His add the whole algorithm is easy to implement, using common approaches.
Figure 2.4 : Flow diagram processing
2.3.1 [c]: Facial Expression Recognition Using Backpropagation .
( Sulistijono et. al., 2008)
Sulistijono and friends in his paper proposed facial expression recognition using backpropagation of neural network. In his work, the motion information is used to detect the face in real time video which is obtained from a camera. The facial detection is used to extract the feature which is useful to recognize a human expression and a human emotion later.
The facial features extracted using edge detection and morphology technique to obtain the lines on the face. Sulistijono used Canny edge detection. Before applying Canny edge detection method, the images will be optimized using brightness and contrast tuning as shown in Figure 2.5.
Figure 2.5 : The image processing (a) Canny edge detection with no contrast and brightness tuning, (b) Canny edge detection with contrast and brightness tuning
2.3.2 Research on Related Work with Different Technique
2.3.2 [a]: A Leaf Recognition Algorithm for Plant Classiï¬cation Using Probabilistic Neural Network (Wu et. al., 2010)
Wu using probability neural network with image and data processing techniques serve the purposes of automatic recognition of common leaves. Twelve leaf characteristics were extracted in 5 of variable of the probability neural network input vector. The probability neural network trained by 1800 leaves to classify 32 types of plants with greater than 90% accuracy. Compared with other approaches, Our algorithm is an appropriate approach to artificial intelligence quick and easy implementation in practice.
2.4 Summary
There are many ways can be used to develop an Herb Recognition by using herbs. Backpropagation has been considering as a best technique for the recognition from image. The capability working on large learning is good for image processing.
CHAPTER 3
METHODOLOGY
This chapter will explain in detail the methodology use in this project. It describes the various methods, techniques and principles in order to create scientific research following the objective from the beginning until all the project phase completed. The purpose of this chapter is to give better understanding about the research field and project scope.
3.1 Research Framework
Theoretical Study
Empirical Study
Architecture Design
Evaluation
In this project, it has been consider four stages of research framework, as in figure 3.1.
Figure 3.1: Stages in Research Framework
The first stage is theoretical study. The purpose of this stage is to gain a basic understanding of physical process. It will be conducted to review the related theories behind. The second stage is Empirical Study. It is a study that derives a data from experiment and observation. The next stage is Architecture design. This stage will represent the structure of the data and program components required to build a computer-based prediction system. The last stage is Evaluation. It will concern about the prototype development, training and testing the system in order to achieve the objective.
3.2 Theoretical Study
Figure 3.2 show the process happen in theoretical study stage:
Literature Research
Journal,
Books,
Thesis,
Internet
Theoretical Study
Detail in Chapter 1:
Project Objective
Project Scope
Project Significant
Project Definition
Literature Review
Part of Plant for recognition
Herb Plant
Literature Survey
Image Processing
Backpropagation
Java
Figure 3.2: Theoretical Study
Target for this stage is to achieve the first objective, "To identify suitable part from herbs plant that can be used for herb recognition". Refer to figure 3.2, theoretical study have two stage, project definition and literature research.
In theoretical study, project definition is a stage of finding basic information about the research such as objective, scope, research question and significant. Project definition will ensure that every work following the right track and prevent from unrelated work of research.
Under literature research, it has two processes. It starts with literature review. It is a process of finding information about herb plant and the unique part from the plant. All the information gained from several sources such as journal, books, articles and thesis. The purpose of this process is to give a clear understanding of herbs plant and more important is to study the each part of plant.
The next process under literature research is literature survey. The important process happen here is finding the suitable part from the herb plant that is unique and can be used for herb recognition. Other than that, literature survey also provide the process of finding suitable intelligent technique that can apply for the project. The survey consist finding the past research that has been done about the domain with different technique and also consider the different domain research but use same technique. From the survey and consider the image processing, backpropagation has been choose as a method in this research. This will explain more in empirical study.
3.3 Empirical Study
Data Management method
Image Processing
Data Representation
Data Training, Testing, & Validation
Data Collection
Empirical Study
Data Analysis
Knowledge representation
Bit String
Figure 3.3 show the four stages of empirical study.
Figure 3.3: Empirical Study
In this stage, the outcome would be collection of the image data. The data will be collected from the image processing technique convert from RGB to Grayscale and then present as a bit string. The real data is needed to ensure the consistency of pattern matching during recognition. Next is knowledge representation stage where the knowledge gained from image represents as a collection of bit string.
3.4 Constructing Architecture Design
Figure 3.4 is describing the procedure in architecture design for this project.
Project Design
Milestone & Gant Chart
Architecture Design
System Architecture
Interface design
Pseudo code and flowchart
Figure 4.4: Architecture Design Phase
The target for this stage is to achieve the second objective, "To design intelligent system for Herb Recognition System". System architecture consists of two parts. First is pseudo code and flowchart design. This part is to design the algorithm for the prediction model. Second is Interface design. Interface is need as a medium of communication between system and user.
3.5 Evaluation
Figure 3.5 shows the procedure for the last stage of this research.
Evaluation
Interaction
User-interface
Image processing
Data preprocessing data
Coding in JSP
Training & testing
Data normalization and representation
Result & analysis
Figure 3.5: Evaluation Stage
Prototype
Purpose for this stage is to achieve the third objective, "To develop Herb Recognition System using Backpropagation neural network". The prototype will be code with Java Server Page (JSP). Before that, the data will preprocess to ensure every rules use for training and testing does not contain any noise. The result from training and testing will be analyst to ensure it return the correct prediction following the rules.
3.6 Summary
This chapter is explaining in detail about the research to construct the study on Herb Recognition. It consist 4 stages of research which is Theoretical study, empirical study, architecture design and evaluation. The next chapter will be doing on empirical study which is the second stage of the research framework.
CHAPTER 4
EMPIRICAL STUDY
In this chapter, the detail of empirical study done for this project is discussed. The detailed explanation on the activities of gathering of information and knowledge needed for the project are also provided.
4.1 Data Collection and Analysis
From Chapter 2, it's has been explain leaf as a part of a plant that suitable to use for recognition process. The collection leaf image will be convert into binary string and then backpropagation will take over the learning and recognition process.
Data collection consists of herb's leaf images and the binary string extract from the image. Every binary string produce from edge detection application develop on java environment and has been prove the accuracy by using Matlab Edge Detection.
4.2 Sample of data
Daun Mas Cotek
Figure 4.1 : Mas Cotek Leaf
Figure 4.1 shows the image of original Mas Cotek Leaf in RGB (Red, Green, Blue) format.
Figure 4.2 : Edge Detection Image
Figure 4.2 shows the converted image from image into binary image by using Edge Detection Convertion in Java application.
Figure 4.3 : Edge Detection from Matlab
Example of Binary String Image
*Refer to appendix A
4.3 Data Management
The data collection will be dividing into two roughly equal-sized sets of vectors. One set was used to training and the other set is use to testing. The ration of dividing is 7:3 where 70% is use for training purpose and 30% for testing.
4.4 Summary
This chapter has been explained the second stage of the research framework. It also shows the sample of data that will be used for the backpropagation nerural network to recognize herbs.
CHAPTER 5
HERB RECOGNITION SYSTEM
In this chapter, detail of the design and development of the system is elaborated and
discussed. Through the end of the chapter, the architecture, algorithm and the system
interface will be shown and discussed.
5.1 System Design
Appendix A
Example of Binary String Image
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111100000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000011111111000000000000000000000011100000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000001111111111100000000000000000000000000000000111000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000011110000000000000000000000000000000000000000000000111000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000011100000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000011100000000000000000000000000000000000000000000000000000000011100000000000000000000000000000000000000000
000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000110000000000000000000000000000000000000000
000000000000000000000000000000000000000000111000000000000000000000001000000000000000000001100000000000000000011000000000000000000000000000000000000000
000000000000000000000000000000000000000011100000000000000000000000001000000000000000000001000000000000000000001100000000000000000000000000000000000000
000000000000000000000000000000000000000110000000000000000000000000001000000000000000000001000000000000000000000110000000000000000000000000000000000000
000000000000000000000000000000000000011000000000000000000000000000010000000000000000000110000000000000000000000011000000000000000000000000000000000000
000000000000000000000000000000000000110000000000000000000000000000010000000000000000000100000000000000000000000001100000000000000000000000000000000000
000000000000000000000000000000000011100000000000000000000000000000100000000000000000000100000000011110000000000000110000000000000000000000000000000000
000000000000000000000000000000000010000000000000000000000000000000110000000000000000000100001111100001000000000000011000000000000000000000000000000000
000000000000000000000000000000000100000000000000000000000001000101101100000000000000000100000100000000100000000000001100000000000000000000000000000000
000000000000000000000000000000001100000000000000000000000001111011000010000000000000001100000100000000100000000000000110000000000000000000000000000000
000000000000000000000000000000011000000000000000000000000011000000000010000000000000000000000010000001000000000000000011000000000000000000000000000000
000000000000000000000000000000010000000000000000000000000010000010000010000010000000000000000010000001000000000000000001000000000000000000000000000000
000000000000000000000000000000100000000000000000000000000000000010000010000010000000000000000010000001000000000000000001100000000000000000000000000000
000000000000000000000000000001100000000000000000000000000000000010000100000001000000000000000010000001000000000000000000100000000000000000000000000000
000000000000000000000000000001000000000000000000000000000000000010000100000000100000000000000010000010000000000000000000010000000000000000000000000000
000000000000000000000000000011000000000000000000000000000000000010000100000000100000000000000010000010000000000000000000011000000000000000000000000000
000000000000000000000000000010000000000000000000000000000000000100000100000000010001000000000010000010000000110000000000001000000000000000000000000000
000000000000000000000000000110000000000000000000000000000000000100000100000000001110100000010000000010000001001000000000001100000000000000000000000000
000000000000000000000000000100000000000000000000000000000000000100000100000000000000100000110000000010000001000100000000000100000000000000000000000000
000000000000000000000000001000000000000000000000000000000000001100000100000000000000010000100000000010000001000010000000000100000000000000000000000000
000000000000000000000000001000000000000000000000000000000000001000000100000000000000010000100000000010000001000010000000000010000000000000000000000000
000000000000000000000000011000000000000000000000000000000000100000000100000000000000010000100000000010000001000010000000000010000000000000000000000000
000000000000000000000000010000000000000000000000000000000000100000001100000000000000010000100000000010000001000010000000000011000000000000000000000000
000000000000000000000000010000000000000000000000000000000001000000001000000000000000010000100000000010000001000010000000000001000000000000000000000000
000000000000000000000000100000000000000000000000000000000001000000001000000000000000010000100000000010000000000100000000000001000000000000000000000000
000000000000000000000000100000000000000000000000000000000001000000001000000000000000010000100000000100000000000100000000000001000000000000000000000000
000000000000000000000000100001000000000000000000000000000001000000001000000000000000010000100000000100000000000100000000000000100000000000000000000000
000000000000000000000001000001000000000000000000000000000001000000001000000000000000010000100000000100000000001100000000000000100000000000000000000000
000000000000000000000001000001000000000000000000000000000001000000001000000000000000010000100000000100000000001000000000000000100000000000000000000000
000000000000000000000001000001000000000000000000000000000001000000001000000000000000010000100000000100000000001000000000000000100000000000000000000000
000000000000000000000001000001000000000000000000000000000001000000011000000000000000010000100000000100000000001000000000000000110000000000000000000000
000000000000000000000010000010000000000000000000000000000011000000010000000000000000010000100000000100000000010000000000000000010000000000000000000000
000000000000000000000010000100000000000000000000000000000010000000010000000000000010010000100000000100000000010000000000000000010000000000000000000000
000000000000000000000010000100000000000000000000000000000010000000010000000000000010010000100000001000000000100000000000000000010000000000000000000000
000000000000000000000010000100000000000000000000000000000010000000100000000000000010010000100000000000000001100000000000001000010000000000000000000000
000000000000000000000100000100000000000000000000000000000010000000100000000000000010110000100000000000000001000000100000001000010000000000000000000000
000000000000000000000100001100000000000000000000000000000010000000100000000000000010000000100000000000000001000000100000001000010000000000000000000000
000000000000000000000100001000000000000000000000000000000010000000010000000000000010000000100000000000000011000000100000001000010000000000000000000000
000000000000000000000100001000000000000000000000000000000010000000010000000000000110000100100000000000000010000001000000001000010000000000000000000000
000000000000000000000100001000000000000000000000000000000100000000010000000000000100100100100000000000000010000001000000001000010000000000000000000000
000000000000000000000100001000000000000000000000000000000100000000010000000000000100010100100000000000000010000010000000001000010000000000000000000000
000000000000000000000100001000000000000000000000000000000100000000001000000000000100010100100000000000000100000010000000001000010000000000000000000000
000000000000000000000100001000000000000000000000000000000100000000001000000000000110010100100000000000001000001100000000001000010000000000000000000000
000000000000000000000100001000000000000000000000000000000100000000001000000000000000010000100000000000001000010000000000001000010000000000000000000000
000000000000000000000100001000000000000000000000000000000100000000001000000000000000010000100000000000001000010000000000010000010000000000000000000000
000000000000000000000100001000000000000000000000000000000100000000001000000000000000010000100000000000001000010000000000010000010000000000000000000000
000000000000000000000100001000000000000000000000000000000100000000001000000000000000010000100000000000001000010000000000010000010000000000000000000000
000000000000000000000100001000000000000000000000000000000101000000001000000000000000010000100000000000000000010000100000100000010000000000000000000000
000000000000000000000100000000000000000000000000000000000001000000001001000000000000010000100000000000000000001111111000010000010000000000000000000000
000000000000000000000100000000000000000000000000000000000001000000001001000000000000010000100000000001000000000000000100100000100000000000000000000000
000000000000000000000010000000000000000000000000000000000000100000001001000000000000010000100000001110000000000000000000100000100000000000000000000000
000000000000000000000010000000000000000000000000000000000000100000001010000000000000010000100000110000000000000000000000100000100000000000000000000000
000000000000000000000010000000000000000000000000000000010000100000001110000000000000010000100001100000000000000000000000100000100000000000000000000000
000000000000000000000010000000000000000000000000000000010000100000001100000000000000010000010011000000000000000000000000100000100000000000000000000000
000000000000000000000010000000000000000000000000000000010000100000001100000000000000010000010110000000000000000000000000100000100000000000000000000000
000000000000000000000010000000000000000000000000000000001000100000001100000000000000100000110000000000000000000000000011000001000000000000000000000000
000000000000000000000010000000000000000000000000000000001000100001111010000000000000100001100000000000000000000000000010000001000000000000000000000000
000000000000000000000001000000000000000000000000000000001000100001100011000000000000100001000000000000000000000000000010000001000000000000000000000000
000000000000000000000001000000000000000000000000000000001000100000100001000000000001000011000000000000000000000000000010000001000000000000000000000000
000000000000000000000001000000000000000000000000000000001000100001000000100000000001000010000000000000000000000000000100000001000000000000000000000000
000000000000000000000001000000000000000000000000000000001000010001000000100000000010000100000000000000000000000000000100000010000000000000000000000000
000000000000000000000001000000000000000000000000000000001000010001000000100000000010000100000000000000000000000000000100000010000000000000000000000000
000000000000000000000000100000000000000000000000000000000100010001000000100000000110000100000000000000000000000000000100000010000000000000000000000000
000000000000000000000000100000000000000000000000000000000100001001000000100000000100001000000000000000000000000000000100000010000000000000000000000000
000000000000000000000000100000000000000000000000000000000100001000000000100000000100001000000000000000000010000000000000000100000000000000000000000000
000000000000000000000000110000000000000000000000000000000100000100000000100000000100010000000000000000000100000000000000000100000000000000000000000000
000000000000000000000000010000000000000000000000000000000110000100000000100000001000010000000000000000000100000000000000000100000000000000000000000000
000000000000000000000000010000000000000000000000000000000010000010000001000000010000100000000000000000000100000000000000001000000000000000000000000000
000000000000000000000000001000000000000000000000000000000001000010000001000000010000100000000000000000000100000000000000001000000000000000000000000000
000000000000000000000000001000000000000000000000000000000001100010000001000000100001100000000000000000001100000000010000011000000000000000000000000000
000000000000000000000000001000000000000000000000000000000000100001000001000000100001000000000000000000000110000000110000010000000000000000000000000000
000000000000000000000000000100000000000000000000000000000000100001000001000001000011000000000000000000000010000000100000110000000000000000000000000000
000000000000000000000000000100000000000000000000000000000000100001000001000001000010000000000000000000000010000000100000100000000000000000000000000000
000000000000000000000000000100000000000000000000000000000000010001000001000010000010000000000000000000000010000000000001100000000000000000000000000000
000000000000000000000000000010000000000000000000000000011111100001000001000000000100000000000000000000000010000001000001000000000000000000000000000000
000000000000000000000000000010000000000000000000000001100000000000010001000000001000000000000000000000000010000010000001000000000000000000000000000000
000000000000000000000000000010000000000000000000000110000000000000010001000000001000000000000000000000000010000010000010000000000000000000000000000000
000000000000000000000000000001000000000000000000001000000000000000010001000000010000000000000000000000000010000010000010000000000000000000000000000000
000000000000000000000000000001000000000000000000001000000000000000011000100000010000000000000000000000000010000010000110000000000000000000000000000000
000000000000000000000000000000100000000000000000001000000000000000001000010000010000000000000000000000000010000000000100000000000000000000000000000000
000000000000000000000000000000100000000000000001110000000000000000000100010000110000000000000000000000000010001000001100000000000000000000000000000000
000000000000000000000000000000010000000000000000000000000000000000000110010000100000000000000000000000000000010000001000000000000000000000000000000000
000000000000000000000000000000010000000000000000000000000000000000100010011001000000000000000000000000000000110000011000000000000000000000000000000000
000000000000000000000000000000001000000000000010000000000000000001100010001001000000000000000000000000000010100000010000000000000000000000000000000000
000000000000000000000000000000001100000000000010000000000000000000110010011001000000000000000000000000000010100000110000000000000000000000000000000000
000000000000000000000000000000000100000000000010000000000000000010010000000011000000000000000000000000000010000000100000000000000000000000000000000000
000000000000000000000000000000000110000000000010000000000000000010010000000010000000000000000000000000000010000001100000000000000000000000000000000000
000000000000000000000000000000000010000000000010000000000000001000000100010000000000000000000000000000000010000001000000000000000000000000000000000000
000000000000000000000000000000000011000000000010000000000000001000000100101000000000000000000000000000000010000001000000000000000000000000000000000000
000000000000000000000000000000000001100000000010000000000000001000000100001000000000000000000000000000000100000010000000000000000000000000000000000000
000000000000000000000000000000000000100000000001000000000000001000000100001000000000000000000000000000000100000010000000000000000000000000000000000000
000000000000000000000000000000000000110000000001000000000000001000000100001000000000000000000000000000001000000100000000000000000000000000000000000000
000000000000000000000000000000000000010000000001000000000000001100000100001000000000000000000000000000000000000100000000000000000000000000000000000000
000000000000000000000000000000000000001000000000000000000000000100000100001000000000000000000000000000000000001000000000000000000000000000000000000000
000000000000000000000000000000000000001100000000000000000000000100000100001000000000000000000000000000000000011000000000000000000000000000000000000000
000000000000000000000000000000000000000110000000000000000000000100000100001000000000000000000000000000000000010000000000000000000000000000000000000000
000000000000000000000000000000000000000010000000000000000000000100000100001000000000000000000000000000000000100000000000000000000000000000000000000000
000000000000000000000000000000000000000011000000000000000000000100000010000100000000000000000000000000000001100000000000000000000000000000000000000000
000000000000000000000000000000000000000001100000000000000000000100000010000100000000000000000000000000000011000000000000000000000000000000000000000000
000000000000000000000000000000000000000000110000000000000000000100000010000100000000000000000000000000000110000000000000000000000000000000000000000000
000000000000000000000000000000000000000000010000000000000000000100000010000100000000000000000000000000000100000000000000000000000000000000000000000000
000000000000000000000000000000000000000000011000000000000000000100000010000100000000000000000001000000001100000000000000000000000000000000000000000000
000000000000000000000000000000000000000000001100000000000000000100000010000100000000000000000000000000011000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000110000000000000000010000010000100000000000000000001000000110000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000010000000000000000110000001000110000000000000000000000001100000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000011000000000000000010000001000010000000000000000000000011000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000001100000000000000010000001000010000000000000000000000010000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000110000000000000010000001000010000000000000000000000100000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000010000000000000010000001000010000000000000000000001100000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000001000000000000010000001100010000000000000000000011000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000001100000000000010000000100010000000000000000000110000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000110000000000010000000100010000010000000000000100000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000011000000000010000000100010000011000000000001100000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000001100000000100000000100001000001000000000011000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000100000001000000000100001000000100000000010000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000010000001000000000100001000000010000000100000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000011000000000000000100001000000000000001100000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000001100000000000000100001000000000000011000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000110000000000000100001000000000000010000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000011000000000000100001000000000000100000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000001100000000000100001000000000001100000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000100000000000100001000000000011000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000010000000000100001000000000010000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000011000000000100001000000000100000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000001100000000010001000000001100000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000110000000010001000000011000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000011000000010001000000110000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000001100000001000000001100000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000110000001000000011000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000011000000000000010000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000110000000000110000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000011111111111000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
