Japan first appeared in written records in AD 57 with the following mention in China's "Book of the Later Han": "Across the ocean from Luoyang are the people of Wa. Formed from more than one hundred tribes, they come and pay tribute frequently. The "Book of Wei", written in the 3rd century, noted the country was the unification of some 30 small tribes or states and ruled by a shaman queen named Himiko of Yamataikoku. During the Han dynasty and Wei dynasty, Chinese travelers to Kyūshū recorded its inhabitants and claimed that they were the descendants of the Grand Count (Tàibó) of the Wu. The inhabitants also show traits of the pre-sinicized Wu people with tattooing, teeth-pulling and baby-carrying. The "Book of Wei" records the physical descriptions which are similar to ones on "Haniwa" statues, such men with braided hair, tattooing and women wearing large, single-piece clothing. Power was often decentralized until the creation of its first constitution in AD 600.